首页 > 代码库 > [codeforces 391D2]Supercollider

[codeforces 391D2]Supercollider

2024-07-16 19:50:13   213人阅读

这题觉得似乎不难的样子……

但硬是没有做出来，真是不知说什么好喵~

注意到没有两条共线的线段具有公共点，没有重合的线段

说明每个十字形最多涉及一个水平线段和一个竖直线段

这说明我们可以二分了:每条线段两端砍掉delta长度后，有没有线段有公共点？

很水的扫描线吧~  按 X 轴扫描，先把横的线段扫进去，再用竖的线段去查询

但是写法是很重要的，我说我不用线段树你信喵？我说我连离散化都不用你信喵？

约大爷教你做人！@Ruchiose
 
  1 #include <cstdio>  2 #include <algorithm>  3 #include <set>  4 const int size=100000;  5   6 namespace IOspace  7 {  8     inline int getint()  9     { 10         register int num=0; 11         register char ch=0, last; 12         do last=ch, ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 13         do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 14         if (last==‘-‘) num=-num; 15         return num; 16     } 17     inline void putint(int num, char ch=‘\n‘) 18     { 19         char stack[10]; 20         register int top=0; 21         if (num==0) stack[top=1]=‘0‘; 22         for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 23         for ( ;top;top--) putchar(stack[top]); 24         if (ch) putchar(ch); 25     } 26 } 27  28 struct line 29 { 30     int x, y, l; 31     inline line() {} 32     inline line(int _x, int _y, int _l):x(_x), y(_y), l(_l) {} 33 }; 34 struct node 35 { 36     int type; 37     int x, y1, y2; 38     inline node() {} 39     inline node(int _type, int _x, int _y1, int _y2):type(_type), x(_x), y1(_y1), y2(_y2) {} 40     inline bool operator < (node a) const {return x!=a.x?x<a.x:type*y2>a.type*a.y2;} 41 }; 42  43 int n, m, k; 44 line h[size], s[size]; 45 node q[size]; 46 std::multiset<int> t; 47 inline int max(int x, int y) {return x>y?x:y;} 48 inline void swap(int & a, int & b) {int t=a; a=b; b=t;} 49 inline bool query(int, int); 50 inline bool check(int); 51  52 int main() 53 { 54     n=IOspace::getint(); m=IOspace::getint(); 55     for (int i=0;i<n;i++) s[i].x=IOspace::getint(), s[i].y=IOspace::getint(), s[i].l=IOspace::getint(); 56     for (int i=0;i<m;i++) h[i].x=IOspace::getint(), h[i].y=IOspace::getint(), h[i].l=IOspace::getint(); 57  58     int left=0, right=0, mid; 59     for (int i=0;i<n;i++) right=max(right, s[i].l); 60     while (left+1<right) 61     { 62         mid=(left+right)>>1; 63         if (check(mid)) left=mid; 64         else right=mid; 65     } 66  67     IOspace::putint(left); 68  69     return 0; 70 } 71  72 inline bool query(int l, int r) 73 { 74     return t.lower_bound(l)!=t.upper_bound(r); 75 } 76 inline bool check(int d) 77 { 78     k=0; 79     for (int i=0;i<m;i++) if (h[i].l>=(d<<1)) 80     { 81         q[k++]=node(1, h[i].x+d, h[i].y, 1); 82         q[k++]=node(1, h[i].x+h[i].l-d, h[i].y, -1); 83     } 84     for (int i=0;i<n;i++) if (s[i].l>=(d<<1)) 85         q[k++]=node(0, s[i].x, s[i].y+d, s[i].y+s[i].l-d); 86     std::sort(q, q+k); 87     t.clear(); 88     for (int i=0;i<k;i++) 89     { 90         if (q[i].type) 91         { 92             if (q[i].y2==1) t.insert(q[i].y1); 93             else t.erase(t.find(q[i].y1)); 94         } 95         else 96             if (query(q[i].y1, q[i].y2)) 97                 return true; 98     } 99     return false;100 }
本傻受益匪浅系列

 

只存操作(包括插入、删除、询问)真是无比的高大上，跪跪跪

还有那鬼畜的查询写法

(set).lower_bound(l)!=(set).upper_bound(r)

可以查询 [l..r] 中是否有数存在，至于为什么这样是对的而不是别的样子了，大家在纸上画画就知道了吧

其实更好理解的是

当 (set).lower_bound(l)==(set).upper_bound(r) 时， [l..r] 中一定没有数

lower_bound是为了将 l 算入 [l..r] 中，upper_bound(r) 也是为了将 r 算入 [l..r] 中

真是跪跪跪跪跪跪跪跪

 


联系
我们