CF1028C Rectangles 思维
2 seconds
256 megabytes
standard input
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 nnrectangles 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.
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.
Print two integers xx and yy — the coordinates of any point that belongs to at least (n−1)(n−1) given rectangles.
3
0 0 1 1
1 1 2 2
3 0 4 1
1 1
3
0 0 1 1
0 1 1 2
1 0 2 1
1 1
4
0 0 5 5
0 0 4 4
1 1 4 4
1 1 4 4
1 1
5
0 0 10 8
1 2 6 7
2 3 5 6
3 4 4 5
8 1 9 2
3 4
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-1个矩形相交区域的点
分析:考虑对于第i个矩形,如果不包括他,前面的i-1个矩形和后面的n-i个矩形是否可以有相交区域,如果有就一定有点处于其中,这个点也就位于n-1个矩形相交区域
我们可以在开始的时候求出前面i个矩形的相交区域pre[i]和后面i个矩形的相交区域pos[i],然后再遍历一次循环求当前矩形前面的矩形和后面矩形的相交区域pre[i-1]相交pos[i+1]
AC代码:
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 232674;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
const double pi = acos(-1.0);
struct node {
ll x1, y1, x2, y2;
};
node a[maxn], pre[maxn], pos[maxn];
int main() {
ll n;
cin >> n;
for( ll i = 1; i <= n; i ++ ) {
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
}
node st = a[1], ed = a[n];
pre[0].x1 = -2e9, pre[0].y1 = -2e9, pre[0].x2 = 2e9, pre[0].y2 = 2e9;
pos[n+1].x1 = -2e9, pos[n+1].y1 = -2e9, pos[n+1].x2 = 2e9, pos[n+1].y2 = 2e9;
for( ll i = 1, j = n; i <= n; i ++, j -- ) {
st.x1 = max(st.x1,a[i].x1), st.y1 = max(st.y1,a[i].y1);
st.x2 = min(st.x2,a[i].x2), st.y2 = min(st.y2,a[i].y2);
pre[i] = st;
ed.x1 = max(ed.x1,a[j].x1), ed.y1 = max(ed.y1,a[j].y1);
ed.x2 = min(ed.x2,a[j].x2), ed.y2 = min(ed.y2,a[j].y2);
pos[j] = ed;
}
for( ll i = 1; i <= n; i ++ ) {
node t;
t.x1 = max(pre[i-1].x1,pos[i+1].x1), t.y1 = max(pre[i-1].y1,pos[i+1].y1);
t.x2 = min(pre[i-1].x2,pos[i+1].x2), t.y2 = min(pre[i-1].y2,pos[i+1].y2);
if( t.x2-t.x1 >= 0 && t.y2-t.y1 >= 0 ) {
cout << t.x1 << " " << t.y1 << endl;
break;
}
}
return 0;
}
最新文章
- JavaScript特性(attribute)、属性(property)和样式(style)
- Unity3D Editor 扩展
- 监听EditText变化---TextWatcher 类用法详解
- nginx源码学习资源(不断更新)
- 一个Socket数据处理模型
- Python学习笔记七-错误和异常
- 转:VC中WORD,DWORD,unsigned long,unsigned short的区别(转)
- 【iOS】Swift扩展extension和协议protocol
- js 将long日期格式 转换为标准日期格式方法
- Python实现LDAP用户名密码验证
- 我的前端故事----来聊聊react-native应用的健康监控
- SSM-SpringMVC-03:SpringMVC执行流程一张有意思的图
- [问题解决]eclipse.ini 文件配置jdk版本
- Vue中splice的使用
- where(泛型类型约束)
- JavaScript之作用域
- [转]Spark学习之路 (三)Spark之RDD
- Pcap4J实现抓包器
- 20165313 《Java程序设计》第八周学习总结
- asp.net url址址中中文汉字参数传递乱码解决方法