前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >AIM Tech Round 5 (rated, Div. 1 + Div. 2)C. Rectangles

AIM Tech Round 5 (rated, Div. 1 + Div. 2)C. Rectangles

作者头像
glm233
发布2020-09-28 10:46:22
2990
发布2020-09-28 10:46:22
举报
文章被收录于专栏:glm的全栈学习之路

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

代码语言:javascript
复制
3
0 0 1 1
1 1 2 2
3 0 4 1

output

Copy

代码语言:javascript
复制
1 1

input

Copy

代码语言:javascript
复制
3
0 0 1 1
0 1 1 2
1 0 2 1

output

Copy

代码语言:javascript
复制
1 1

input

Copy

代码语言:javascript
复制
4
0 0 5 5
0 0 4 4
1 1 4 4
1 1 4 4

output

Copy

代码语言:javascript
复制
1 1

input

Copy

代码语言:javascript
复制
5
0 0 10 8
1 2 6 7
2 3 5 6
3 4 4 5
8 1 9 2

output

Copy

代码语言:javascript
复制
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个矩形(或者在n个矩形)中的点

思路:维护两个数组 前缀 后缀 表示前i个矩形交的小矩形,

然后遍历一遍如果去掉某第i个矩形那么它的前缀i-1和后缀i+1这两个小矩形再取一次交,如果合法(就是两个矩形相交)就找到了

代码语言:javascript
复制
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 200005
const double eps = 1e-6;
using namespace std;
inline ll read()
{
	char ch = getchar(); ll s = 0, w = 1;
	while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	return s * w;
}
inline void write(ll x)
{
	if (x < 0)putchar('-'), x = -x;
	if (x > 9)write(x / 10);
	putchar(x % 10 + 48);
}
ll n;
struct node
{
    ll x1=-inf,y1=-inf,x2=inf,y2=inf;
}a[maxn],pre[maxn],suf[maxn];
int main()
{
    cin>>n;
    for(rg i=1;i<=n;i++)
    {
        a[i].x1=read(),a[i].y1=read(),a[i].x2=read(),a[i].y2=read();
    }
    for(rg i=1;i<=n;i++)
    {
        pre[i].x1=max(pre[i-1].x1,a[i].x1);
        pre[i].y1=max(pre[i-1].y1,a[i].y1);
        pre[i].x2=min(pre[i-1].x2,a[i].x2);
        pre[i].y2=min(pre[i-1].y2,a[i].y2);
    }
      for(rg i=n;i>=1;i--)
    {
        suf[i].x1=max(suf[i+1].x1,a[i].x1);
        suf[i].y1=max(suf[i+1].y1,a[i].y1);
        suf[i].x2=min(suf[i+1].x2,a[i].x2);
        suf[i].y2=min(suf[i+1].y2,a[i].y2);
    }
    for(rg i=1;i<=n;i++)
    {
        ll temp1=-inf,temp2=-inf,temp3=inf,temp4=inf;
        temp1=max(pre[i-1].x1,suf[i+1].x1);
        temp2=max(pre[i-1].y1,suf[i+1].y1);
        temp3=min(pre[i-1].x2,suf[i+1].x2);
        temp4=min(pre[i-1].y2,suf[i+1].y2);
        if(temp1<=temp3&&temp2<=temp4)
        {
            cout<<temp1<<" "<<temp2<<endl;
            return 0;
        }
    }
   	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/09/09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档