P16101 [ICPC 2019 NAIPC] Intersecting RectanglesLink: https://www.luogu.com.cn/problem/P16101题目描述给定二维平面上的n nn个轴对齐矩形。在本问题中如果两个矩形的边界存在任何公共点则认为它们相交特别地一个矩形完全包含另一个矩形不算相交。请判断是否存在一对相交的矩形。在该示例中只有矩形A和B相交。输入格式每个测试用例的第一行包含一个整数n nn1 ≤ 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​≤109x 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输入 #13 0 0 2 2 1 1 3 4 5 7 6 8输出 #11输入输出样例 #2输入 #24 0 0 20 20 1 1 3 4 2 10 9 12 11 3 19 18输出 #20Solution1. 题意输入若干个矩形每个矩形通过其一对对角的坐标描述判断是否存在某两个矩形相交。2. 分析核心思想是扫描线。由于题目保证了所有矩形的x xx坐标互不相同所有y yy坐标也互不相同。因此在坐标全不相同的前提下如果有相交则必然是一个矩形的水平边与另一个矩形的垂直边出现交叉。题目里提到的共顶点或者公共边之类的情况均不会出现。扫描线思想的核心是在输入过程中一边输入一边维护“活跃”即可能发生相交的矩形核心步骤是沿x xx轴从左到右扫描。将每个矩形的左右两条边拆分为左边界事件和右边界事件对于左边界事件将当前矩形的上下两条水平边的y yy坐标加入活跃集合对于右边界事件查询当前矩形的垂直边( y 1 , y 2 ) (y_1, y_2)(y1​,y2​)是否与集合中已有的水平边相交然后将该矩形的两条水平边从集合中移除表示这个矩形结束这段y yy区间不再活跃判断是否相交。垂直边与水平边相交等价于活跃集合中存在一个y yy满足y 1 y y 2 y_1 y y_2y1​yy2​。上面是对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. 代码#includebits/stdc.husingnamespacestd;structEvent{longlongx;inttype;// 1: 左边界, 2: 右边界longlongy1,y2;// 矩形在 y 轴上的范围};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn))return0;vectorEventevents;events.reserve(2*n);for(inti0;in;i){longlongx1,y1,x2,y2;cinx1y1x2y2;events.push_back({x1,1,y1,y2});events.push_back({x2,2,y1,y2});}sort(events.begin(),events.end(),[](constEventa,constEventb){returna.xb.x;});setlonglongactive_ys;boolintersectfalse;for(constautoev:events){if(ev.type1){active_ys.insert(ev.y1);active_ys.insert(ev.y2);}autoitactive_ys.upper_bound(ev.y1);if(it!active_ys.end()*itev.y2){intersecttrue;break;}if(ev.type2){active_ys.erase(ev.y1);active_ys.erase(ev.y2);}}cout(intersect?1:0)\n;return0;}