codeforces 1028C Rectangles(枚举)
C. Rectangles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given nn rectangles on a plane with coordinates of their bottom left and upper right points. Some (n−1)(n−1) of the given nn rectangles have some common point. A point belongs to a rectangle if this point is strictly inside the rectangle or belongs to its boundary.
Find any point with integer coordinates that belongs to at least (n−1)(n−1) given rectangles.
Input
The first line contains a single integer nn (2≤n≤1326742≤n≤132674) — the number of given rectangles.
Each the next nn lines contains four integers x1x1, y1y1, x2x2 and y2y2 (−109≤x1<x2≤109−109≤x1<x2≤109, −109≤y1<y2≤109−109≤y1<y2≤109) — the coordinates of the bottom left and upper right corners of a rectangle.
Output
Print two integers xx and yy — the coordinates of any point that belongs to at least (n−1)(n−1) given rectangles.
Examples
input
Copy
3 0 0 1 1 1 1 2 2 3 0 4 1
output
Copy
1 1
input
Copy
3 0 0 1 1 0 1 1 2 1 0 2 1
output
Copy
1 1
input
Copy
4 0 0 5 5 0 0 4 4 1 1 4 4 1 1 4 4
output
Copy
1 1
input
Copy
5 0 0 10 8 1 2 6 7 2 3 5 6 3 4 4 5 8 1 9 2
output
Copy
3 4
Note
The picture below shows the rectangles in the first and second samples. The possible answers are highlighted.
The picture below shows the rectangles in the third and fourth samples.
题意:给你n(n<1.4e5)个矩形的左上角和右下角点的坐标(-1e9<=x,y<=1e9),求任意一个点,被其中的至少(n-1)个矩形覆盖。
思路:枚举。想这道题的时候思维僵化了。
给出两个矩形左上角和右下角的两个点,求这两个矩形的并:
(max(a.xl,b.xl),max(a.yl,b.yl)) 就是交矩形的左上角坐标。
(min(a.xr,b.xr),min(a.yr,b.yr)) 就是交矩形的右下角坐标。
判断合法只需要看新的xl,xr,yl,yr是否是一个矩形即可。
然后关键是至少被n-1个点覆盖:枚举哪一个矩形不覆盖这个点即可。即处理一下前缀交,后缀交,然后枚举一下中点即可。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
const ll inf=2147483647;
int n,m,k;
ll ans,x,y,tmp,cnt;
struct node
{
ll xl,yl,xr,yr;
}a[maxn],aa,l[maxn],r[maxn];
bool jud(node aa)
{
if(aa.xl>aa.xr)return 0;
if(aa.yl>aa.yr)return 0;
else return 1;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld%lld",&a[i].xl,&a[i].yl,&a[i].xr,&a[i].yr);
l[0].xl=l[0].yl=-inf;
l[0].xr=l[0].yr=inf;
for(int i=1;i<=n;i++)
{
l[i].xl=max(a[i].xl,l[i-1].xl);
l[i].yl=max(a[i].yl,l[i-1].yl);
l[i].xr=min(a[i].xr,l[i-1].xr);
l[i].yr=min(a[i].yr,l[i-1].yr);
}
r[n+1].xl=r[n+1].yl=-inf;
r[n+1].xr=r[n+1].yr=inf;
for(int i=n;i>=1;i--)
{
r[i].xl=max(a[i].xl,r[i+1].xl);
r[i].yl=max(a[i].yl,r[i+1].yl);
r[i].xr=min(a[i].xr,r[i+1].xr);
r[i].yr=min(a[i].yr,r[i+1].yr);
}
if(jud(l[n-1])){
printf("%lld %lld\n",l[n-1].xl,l[n-1].yl);
}
else if (jud(r[2]))
{
printf("%lld %lld\n",r[2].xl,r[2].yl);
}
else for(int i=2;i<=n-1;i++)
{
aa.xl=max(l[i-1].xl,r[i+1].xl);
aa.yl=max(l[i-1].yl,r[i+1].yl);
aa.xr=min(l[i-1].xr,r[i+1].xr);
aa.yr=min(l[i-1].yr,r[i+1].yr);
if(jud(aa))
{
printf("%lld %lld\n",aa.xl,aa.yl);
break;
}
}
}
return 0;
}
上一篇: 使用TimerTask的坑
下一篇: 基于Python创建语音识别控制系统
推荐阅读
-
B. Power Sequence(数学+枚举)Codeforces Round #666 (Div. 2)
-
CodeForces - 908C (暴力枚举)
-
Codeforces 1028C(面积并/思维)
-
Codeforces 1321 C. Remove Adjacent(贪心枚举)
-
CodeForces - 764D Timofey and rectangles
-
Codeforces Round #661 C. Boats Competition(思维+暴力枚举)
-
CodeForces - 761C Dasha and Password CodeForces (枚举)
-
Codeforces 1020C. Elections 枚举
-
codeforces 1395C(暴力枚举)
-
Codeforces Round #489 (Div. 2) B. Nastya Studies Informatics(数学+枚举优化)