打卡信奥刷题（3096）用C++实现信奥题 P7181 [BalticOI 2004] Rectangles (Day2)

P7181 [BalticOI 2004] Rectangles (Day2)题目描述平面上有n nn个矩形。矩形边平行于坐标轴。这些长方形可以重叠、重合或相互分离。它们的顶点坐标( x , y ) (x,y)(x,y)中x , y x,yx,y都是非负整数横坐标不超过x max ⁡ x_{\max}xmax​纵坐标不超过y max ⁡ y_{\max}ymax​。A AA点位于( 0 , 0 ) (0,0)(0,0)若C ( x max ⁡ , 0 ) , D ( 0 , y max ⁡ ) , E ( x max ⁡ , y max ⁡ ) C(x_{\max},0),D(0,y_{\max}),E(x_{\max},y_{\max})C(xmax​,0),D(0,ymax​),E(xmax​,ymax​)则B BB点位于线段C E CECE或D E DEDE上。线段A B ABAB可能与矩形相交即使只与一个矩形顶点相交也视为相交。你需要找到一个B BB点使与线段A B ABAB相交的矩形尽可能多。输入格式第一行三个整数x max ⁡ , y max ⁡ , n x_{\max},y_{\max},nxmax​,ymax​,n。接下来n nn行每行四个整数分别表示第i ii个矩形的左下角坐标与右上角坐标。输出格式一行三个整数分别为最多的相交矩形数此时B BB点坐标。如果有多种方案输出任意一种。输入输出样例 #1输入 #122 14 8 1 8 7 11 18 10 20 12 17 1 19 7 12 2 16 3 16 7 19 9 8 4 12 11 7 4 9 6 10 5 11 6输出 #15 22 12说明/提示样例 1 说明输出也可以为5 22 11。数据规模与约定对于100 % 100\%100%的数据有1 ≤ n ≤ 10 4 1\le n\le 10^41≤n≤1040 ≤ x max ⁡ , y max ⁡ ≤ 10 9 0\le x_{\max},y_{\max}\le 10^90≤xmax​,ymax​≤109。说明译自 BalticOI 2004 Day2 B Rectangles。特别感谢感谢 tiger2005 提供的 SPJC实现#includeiostream#includecstdio#includealgorithm#includecmathusingnamespacestd;typedeflonglongll;constintmaxn1e45;intn,m,a,b,c,d,X,Y,tot,ans;ll p,q,pos;ll l[maxn],r[maxn],tmp[maxn1],sum[maxn1];intmain(){scanf(%d %d %d,X,Y,n);for(inti1;in;i){scanf(%d %d %d %d,a,b,c,d);pceil((double)Y*a/d),qfloor((double)X*d/a);l[i](pX)?p:XY-q;pfloor((double)Y*c/b),qceil((double)X*b/c);r[i](pX)?p:XY-q;tmp[tot]l[i];tmp[tot]r[i];}sort(tmp1,tmp1tot);munique(tmp1,tmp1tot)-tmp;for(inti1;in;i){l[i]lower_bound(tmp1,tmp1m,l[i])-tmp;r[i]lower_bound(tmp1,tmp1m,r[i])-tmp;sum[l[i]];sum[r[i]1]--;}for(inti1;im;i){sum[i]sum[i-1];if(sum[i]ans){anssum[i];postmp[i];}}printf(%d ,ans);if(posX)printf(%lld %d\n,pos,Y);elseprintf(%d %lld\n,X,XY-pos);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容