首页 > 代码库 > [bzoj2961] 共点圆
[bzoj2961] 共点圆
Description
在平面直角坐标系中，Wayne需要你完成n次操作，操作只有两种：
1.0 x y。表示在坐标系中加入一个以(x, y)为圆心且过原点的圆。
2.1 x y。表示询问点(x, y)是否在所有已加入的圆的内部（含圆周），且至少在一个圆内部（含圆周）。
为了减少你的工作量，题目保证圆心严格在x轴上方（纵坐标为正），且横坐标非零。
Input
第1行一个整数n。
接下来n行，每行第一个数是0或1，分别表示两种操作。
接着有两个实数x和y，具体意义见题面。
Output
对于每个询问操作，如果点在所有已加入的圆内（或圆周上），则输出“Yes”（不含引号）；否则输出“No”（不含引号）。
Sample Input
5
0 2.0000 3.0000
0 4.0000 1.0000
1 1.000000 1.000000
0 -3.0000 2.0000
1 1.000000 1.000000
Sample Output
Yes
No
n≤500000，所有坐标绝对值不超过10000。
输入数据保证圆心纵坐标为正，横坐标非零。
CDQ分治..这几天重新学了一下发现自己还是不怎么会..
首先问题可以变成，每次给个半平面，询问是否所有圆心都在它里面。
具体该在上凸包还是下凸包查就看推出来的式子了..
主要是这题数据范围有点大，CDQ的时候不能多带log...
要线性建区间[l,mid]里点的凸包的话，得使[l,mid]里的点x坐标有序；要线性查询[mid+1,r]里所有询问的话，得让[mid+1,r]里询问的斜率有序；而输入顺序本身又有一维。。
所以最开始按照斜率排一下序，每次分治时按输入顺序分到左右两边，先处理[l,mid]，然后再建凸包处理[mid+1,r]里的询问，最后把[l,r]按照x坐标归并排序一下...就都满足了..
如果每次建凸包不是重新建，而是把两个小的合成一个大的，似乎就不用想那么多了？
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<cstdlib> 7 #include<queue> 8 #define ll long long 9 #define ui unsigned int 10 #define d double 11 using namespace std; 12 const int maxn=500023;const d eps=1e-7; 13 struct zsq{bool ask;int id;d x,y,k;}q[maxn]; 14 struct zstb{int l,r;}stb[maxn],xtb[maxn];int tot; 15 int st[maxn<<1],TOP,dl[maxn],tmpdl[maxn]; 16 int i,j,k,n,m; 17 bool gg[maxn],ask[maxn]; 18 19 int ra,fh;char rx; 20 inline int read(){ 21 rx=getchar(),ra=0,fh=1; 22 while(rx!=‘-‘&&(rx<‘0‘||rx>‘9‘))rx=getchar(); 23 if(rx==‘-‘)fh=-1,rx=getchar(); 24 while(rx>=‘0‘&&rx<=‘9‘)ra=ra*10+rx-48,rx=getchar();return ra*fh; 25 } 26 27 inline d getk(int a,int b){return (q[b].y-q[a].y)/(q[b].x-q[a].x);} 28 inline bool istb(int a,int b,int c,bool isstb){ 29 if(isstb)return (q[c].x-q[b].x)*(q[b].y-q[a].y) > (q[b].x-q[a].x)*(q[c].y-q[b].y); 30 else return (q[b].x-q[a].x)*(q[c].y-q[b].y) > (q[c].x-q[b].x)*(q[b].y-q[a].y); 31 } 32 33 inline bool check(int a,int b){//点b在圆a内 34 // printf("check: %d %d %.2lf %.2lf\n",a,b,q[a].x*q[a].x+q[a].y*q[a].y , (q[a].x-q[b].x)*(q[a].x-q[b].x)+(q[a].y-q[b].y)*(q[a].y-q[b].y)); 35 return q[a].x*q[a].x+q[a].y*q[a].y +eps > (q[a].x-q[b].x)*(q[a].x-q[b].x)+(q[a].y-q[b].y)*(q[a].y-q[b].y); 36 } 37 inline void buildtb(int x,int l,int r){ 38 int i; 39 // printf("buildtb:");for(i=l;i<=r;i++)if(!q[dl[i]].ask)printf(" (%.2lf,%.2lf)",q[dl[i]].x,q[dl[i]].y);puts(""); 40 41 stb[x].l=TOP+1; 42 for(i=l;i<=r;i++)if(!q[dl[i]].ask){ 43 while(TOP>stb[x].l&&!istb(st[TOP-1],st[TOP],dl[i],1))TOP--; 44 if(TOP>=stb[x].l&&q[st[TOP]].x==q[dl[i]].x) 45 if(q[dl[i]].y>q[st[TOP]].y)TOP--;else continue; 46 st[++TOP]=dl[i]; 47 }stb[x].r=TOP; 48 49 xtb[x].l=TOP+1; 50 for(i=l;i<=r;i++)if(!q[dl[i]].ask){ 51 while(TOP>xtb[x].l&&!istb(st[TOP-1],st[TOP],dl[i],0))TOP--; 52 if(TOP>=xtb[x].l&&q[st[TOP]].x==q[dl[i]].x) 53 if(q[dl[i]].y<q[st[TOP]].y)TOP--;else continue; 54 st[++TOP]=dl[i]; 55 }xtb[x].r=TOP; 56 } 57 void solve(int l,int r){ 58 if(l==r)return; 59 int i,x=++tot,mid=l+r>>1,r1=l,r2=mid+1; 60 61 for(i=l;i<=r;i++)if(q[dl[i]].id<=mid)tmpdl[r1++]=dl[i];else tmpdl[r2++]=dl[i]; 62 memcpy(dl+l,tmpdl+l,(r-l+1)<<2);solve(l,mid); 63 // printf("solve:%d--%d\n",l,r); 64 // for(i=l;i<=r;i++)printf(" %d",dl[i]);puts(""); 65 66 TOP=0,buildtb(x,l,mid);int top1=stb[x].r,top2=xtb[x].l,now; 67 // printf("STB: ");for(i=stb[x].l;i<=stb[x].r;i++)printf(" (%.2lf,%.2lf)",q[st[i]].x,q[st[i]].y);puts(""); 68 // printf("XTB: ");for(i=xtb[x].l;i<=xtb[x].r;i++)printf(" (%.2lf,%.2lf)",q[st[i]].x,q[st[i]].y);puts(""); 69 if(stb[x].l<=stb[x].r) 70 for(i=mid+1;i<=r;i++)if(q[now=dl[i]].ask&&!gg[q[now].id]&&q[now].y!=0){ 71 if(q[now].y<0){ 72 while(top1>stb[x].l&&getk(st[top1-1],st[top1])<=q[now].k)top1--; 73 if(!check(st[top1],now))gg[q[now].id]=1; 74 }else{ 75 while(top2<xtb[x].r&&getk(st[top2],st[top2+1])<=q[now].k)top2++; 76 if(!check(st[top2],now))gg[q[now].id]=1; 77 } 78 } 79 solve(mid+1,r); 80 81 r1=l,r2=mid+1; 82 for(i=l;i<=r;i++)tmpdl[i]=((q[dl[r1]].x<=q[dl[r2]].x&&r1<=mid)||r2>r)?dl[r1++]:dl[r2++]; 83 memcpy(dl+l,tmpdl+l,(r-l+1)<<2); 84 } 85 86 bool operator <(zsq a,zsq b){return a.k<b.k;} 87 int main(){ 88 n=read();d mxx=-1e9,mnx=1e9; 89 for(i=1;i<=n;i++){ 90 q[i].ask=ask[i]=read(),gg[i]=!q[i].ask, 91 scanf("%lf%lf",&q[i].x,&q[i].y); 92 if(!q[i].y){ 93 if(q[i].x>0)gg[i]=mnx*2<eps+q[i].x; 94 if(q[i].x<0)gg[i]=mxx*2>eps+q[i].x; 95 }else q[i].k=-q[i].x/q[i].y; 96 if(!q[i].ask)mxx=max(mxx,q[i].x),mnx=min(mnx,q[i].x); 97 q[i].id=dl[i]=i; 98 } 99 sort(q+1,q+1+n); 100 // for(i=1;i<=n;i++){ 101 // if(q[dl[i]].ask)printf("ask:");else printf("ins:"); 102 // printf(" %.2lf,%.2lf k:%.2lf\n",q[i].x,q[i].y,q[i].k); 103 // } 104 solve(1,n); 105 // for(i=1;i<=n;i++)printf(" (%.2lf,%.2lf)",q[dl[i]].x,q[dl[i]].y);puts(""); 106 // TOP=0,++tot,buildtb(tot,1,n);for(i=xtb[tot].l;i<=xtb[tot].r;i++)printf(" (%.2lf,%.2lf)",q[st[i]].x,q[st[i]].y);puts(""); 107 bool flag=0; 108 for(i=1;i<=n;i++)if(!ask[i])flag=1;else puts((flag&&!gg[i])?"Yes":"No"); 109 }
[bzoj2961] 共点圆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。