企业官网建设流程全解析

P16101 [ICPC 2019 NAIPC] Intersecting Rectangles

Link: https://www.luogu.com.cn/problem/P16101

题目描述

给定二维平面上的n nn个轴对齐矩形。在本问题中，如果两个矩形的边界存在任何公共点，则认为它们相交（特别地，一个矩形完全包含另一个矩形不算相交）。请判断是否存在一对相交的矩形。

在该示例中，只有矩形A和B相交。

输入格式

每个测试用例的第一行包含一个整数n nn（1 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤105），表示矩形的数量。

接下来的n nn行，每行包含四个空格分隔的整数：

x 1 y 1 x 2 y 2 x_1\ y_1\ x_2\ y_2x1​y1​x2​y2​

（− 10 9 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10 9 -10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9−109≤x1​,y1​,x2​,y2​≤109，x 1 < x 2 x_1 < x_2x1​<x2​，y 1 < y 2 y_1 < y_2y1​<y2​），描述一个矩形，其中( x 1 , y 1 ) (x_1, y_1)(x1​,y1​)是左下角，( x 2 , y 2 ) (x_2, y_2)(x2​,y2​)是右上角。所有x xx坐标互不相同，所有y yy坐标也互不相同。

输出格式

输出一个整数，如果存在一对相交的矩形，则输出1 11，否则输出0 00。

输入输出样例 #1

输入 #1

3 0 0 2 2 1 1 3 4 5 7 6 8

输出 #1

1

输入输出样例 #2

输入 #2

4 0 0 20 20 1 1 3 4 2 10 9 12 11 3 19 18

输出 #2

0

Solution

1. 题意

输入若干个矩形（每个矩形通过其一对对角的坐标描述），判断是否存在某两个矩形相交。

2. 分析

核心思想是扫描线。

由于题目保证了所有矩形的x xx坐标互不相同，所有y yy坐标也互不相同。因此在坐标全不相同的前提下，如果有相交，则必然是一个矩形的水平边与另一个矩形的垂直边出现交叉。题目里提到的共顶点或者公共边之类的情况均不会出现。

扫描线思想的核心是在输入过程中，一边输入一边维护“活跃”（即：可能发生相交）的矩形，核心步骤是：

1. 沿x xx轴从左到右扫描。将每个矩形的左右两条边拆分为左边界事件和右边界事件；
2. 对于左边界事件，将当前矩形的上下两条水平边的y yy坐标加入活跃集合；
3. 对于右边界事件，查询当前矩形的垂直边( y 1 , y 2 ) (y_1, y_2)(y1​,y2​)是否与集合中已有的水平边相交，然后将该矩形的两条水平边从集合中移除（表示这个矩形结束，这段y yy区间不再活跃）；
4. 判断是否相交。垂直边与水平边相交等价于活跃集合中存在一个y yy满足y 1 < y < y 2 y_1 < y < y_2y1​<y<y2​。

上面是对x xx扫描的总体过程，对y yy扫描也可以，不再赘述。

使用集合数据结构维护活跃的y yy坐标，再利用二分查找（也就是upper_bound）即可在O ( log ⁡ n ) O(\log n)O(logn)时间内完成查询。

最后总体的时间复杂度就是O ( n log ⁡ n ) O(n \log n)O(nlogn)。

3. 代码

#include<bits/stdc++.h>usingnamespacestd;structEvent{longlongx;inttype;// 1: 左边界, 2: 右边界longlongy1,y2;// 矩形在 y 轴上的范围};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cin>>n))return0;vector<Event>events;events.reserve(2*n);for(inti=0;i<n;++i){longlongx1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;events.push_back({x1,1,y1,y2});events.push_back({x2,2,y1,y2});}sort(events.begin(),events.end(),[](constEvent&a,constEvent&b){returna.x<b.x;});set<longlong>active_ys;boolintersect=false;for(constauto&ev:events){if(ev.type==1){active_ys.insert(ev.y1);active_ys.insert(ev.y2);}autoit=active_ys.upper_bound(ev.y1);if(it!=active_ys.end()&&*it<ev.y2){intersect=true;break;}if(ev.type==2){active_ys.erase(ev.y1);active_ys.erase(ev.y2);}}cout<<(intersect?1:0)<<"\n";return0;}