首页 > 其他分享 >洛谷 P11011 点的覆盖

洛谷 P11011 点的覆盖

时间:2024-08-31 13:25:25浏览次数:13  
标签:ymin 洛谷 覆盖 min int ll xmin 矩形 P11011

洛谷 P11011 点的覆盖

题意

给定一个四边平行于坐标轴的矩形 \(A\),给定 \(n\) 个在矩形 \(A\) 内部(可能在边缘上)的点。

求有多少个 \(A\) 的子矩形覆盖了所有 \(n\) 个点(允许在边缘上)。

所有坐标都是整数。

思路

求出:\(X_1=\max_{i=1}^n x_i\),\(X_2=\min_{i=1}^n x_i\),\(Y_1=\max_{i=1}^n y_i\),\(Y_2=\min_{i=1}^n y_i\)。

记矩形左上角坐标为 \((x,y)\),右下角坐标为 \((X,Y)\),设点 \(P(X_2,Y_1)\) 和 \(Q(X_1,Y_2)\) 如图:

容易发现子矩形的左上角只能在左上角的黑色矩形中,右下角只能在右下角的黑色矩形中。

算出两个矩形中有多少个整点,相乘即可。

左上角为 \((x,y)\),右下角为 \((X,Y)\) 的矩形中整点的个数为 \((X-x+1)(y-Y+1)\)。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, X1, Y1, X2, Y2;
int xmax, xmin, ymax, ymin;
int main() {
	cin >> n >> X1 >> Y1 >> X2 >> Y2;
	xmin = ymin = 1e9;
	for (int i = 1, x, y; i <= n; i ++) {
		cin >> x >> y;
		xmin = min(xmin, x);
		xmax = max(xmax, x);
		ymin = min(ymin, y);
		ymax = max(ymax, y); 
	}
	ll z = (xmin - X1 + 1) * (Y1 - ymax + 1) % mod;
	ll y = (X2 - xmax + 1) * (ymin - Y2 + 1) % mod;
	ll ans = z * y % mod;
	cout << ans << "\n";
	return 0;
}

标签:ymin,洛谷,覆盖,min,int,ll,xmin,矩形,P11011
From: https://www.cnblogs.com/maniubi/p/18390180

相关文章

  • 【C++】单元测试覆盖率工具lcov的使用
    本文首发于❄️慕雪的寒舍本文讲述了如何在C++代码中使用单元测试覆盖率工具lcov,以及gcov命令的使用。版本是lcov2.0和gcov11.4.0。写在前面:lcov是我在实习期间初次接触到的工具,当时在配置的时候就遇到了大量中文互联网没有任何记录的问题。绝大部分博客对lcov工具的......
  • 金矢留学对话曼彻斯特城市大学:语言环境优越,奖学金覆盖广
    金矢留学:老师上午好,欢迎来参加金矢留学的渠道答谢活动,可以先请您介绍一下自己以及介您所代表的大学吗?曼彻斯特城市大学中国办公室招生官CeciliaLei:您好,我叫Cecilia,是曼彻斯特城市大学中国办公室的招生官,介绍学校之前可以先介绍一下我们办公室,因为我们办公室可能跟很多大学的中国办......
  • 洛谷题单指南-常见优化技巧-P1950 长方形
    原题链接:https://www.luogu.com.cn/problem/P1950题意解读:在一张n*m个格子的纸上,从没有画过的格子中剪出长方形的方案数。解题思路:1、暴力做法枚举所有的子矩阵O(n^4),然后用二维前缀和计算子矩阵的和,通过和来判断子矩阵是否全部是'.'。2、优化做法针对每一行进行处理,计算包......
  • 洛谷 P2680 [NOIP2015 提高组] 运输计划
    洛谷P2680[NOIP2015提高组]运输计划题意给出一棵树和\(m\)条路径,可以选择一条边,把边权改为\(0\),求\(m\)条路经长度最大值的最小值。思路看到最大值最小,可以想到二分答案,答案具有单调性。考虑如何判定答案\(x\)是否可行。统计所有长度大于\(x\)的路径,统计它们共......
  • 【C++二分查找】2271. 毯子覆盖的最多白色砖块数
    本文涉及的基础知识点C++二分查找LeetCode2271.毯子覆盖的最多白色砖块数给你一个二维整数数组tiles,其中tiles[i]=[li,ri],表示所有在li<=j<=ri之间的每个瓷砖位置j都被涂成了白色。同时给你一个整数carpetLen,表示可以放在任何位置的一块毯子的长度......
  • 线段覆盖问题
    1.线段不覆盖问题给出\(n\)个线段,选择尽量多的线段使得线段无重叠,问最多可以选多少条线段。解析考虑贪心,将线段按右端点从小到大排序,如果这条线段的左端点大于上一条线段的右端点那就选择这条线段。为什么这么贪是对的呢,因为将右端点排序可以使右边剩余的空间尽量大,那么剩余......
  • 洛谷P5322 [BJOI2019] 排兵布阵 题解
    代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongintdp[20001],a[101][101],s,n,m;signedmain(){ cin>>s>>n>>m; for(intj=1;j<=s;j++){ for(inti=1;i<=n;i++){ cin>>a[i][j]; } } for(inti=1;......
  • 优化拓展Camstar原生弹窗提示,解决原生消息提示无效或被覆盖的场景
    1.参考代码如下 1usingCamstar.WebPortal.PortalFramework;2usingSystem;3usingSystem.Web.UI;45namespaceCamstar.WebPortal.WebPortlets.Shopfloor6{7///<summary>8///優化拓展Camstar原生消息彈窗提示,解決原生消息提示無效或被覆蓋......
  • 洛谷P9751 [CSP-J 2023] 旅游巴士
    传送门:P9751[CSP-J2023]旅游巴士为了那个梦我们扬帆起航,为了理所到来的那天跨越无尽黑夜由于这几天做的题目太少,我用小号立下flag:导致果然做了一晚上。。。。并且最后还是没做出来被我妈强制去睡觉了题目意思:题目很明白了,这里说几个要注意的点:道路均只能单向通行到......
  • 洛谷 P3128 [USACO15DEC] Max Flow P
    洛谷P3128[USACO15DEC]MaxFlowP题意给定一棵\(n\)个点的树,给定\(k\)个点对\((u,v)\),把\(u\)到\(v\)路径上所有点的点权加一,最后求最大点权。思路树上差分模版。维护\(a_i\)表示每个点到根的加法标记。对于每个点对\((u,v)\),把\(a_u\),\(a_v\)加一,\(a_{LCA......