题解 【P5525 [Ynoi2012] WC2016充满了失望】

**题意** ： 给出平面上的一个点集 $S$ 。 给出平面上的若干个圆，对于每个圆，判定其是否完全在 $S$ 的凸包的内部。 保证圆的半径变化不超过 $1$ 时答案不发生变化。 $n,m\leq 5\times 10^5$，时限 $\texttt{2s}$。 ------------ 将凸包拆分成上凸壳和下凸壳。我们只需分别判断圆是否在 上/下 凸壳内部。 下面只介绍上凸壳，将 $y$ 坐标翻转即可转化为下凸壳。 记 ${\rm convex}(S)$ 为点集 $S$ 的上凸壳（内部的区域）。 记 ${\rm contract}(T,r)$ 表示能完全放入平面区域 $T$ 中的半径为 $r$ 的圆的圆心的集合。 考虑随着 $r$ 的增大 ${\rm contract}\big({\rm convex}(S),r\big)$ 会如何变化。 若将 ${\rm convex}(S)$ 描述为半平面交，则变化相当于每个半平面缩小了 $r$ 单位距离。 在这个过程中，有些半平面可能不再在凸壳上，需要将其删除。 每个半平面只可能被两侧的半平面迫害掉，用**堆**维护每个半平面被迫害掉的时间。 如何计算 $l_1,l_3$ 迫害 $l_2$ 所需时间？ 这是初中数学基础题：做两条角平分线，取交点到 $l_2$ 的距离。  当某个半平面被删除时，重新计算两侧的半平面的迫害时间。 对于一个正确的收缩凸壳，容易**二分**判定圆心是否在其中。 用**并查集**维护序列，能支持删除某个元素，快速查找某个元素的前后继。 复杂度 $O\big((n+m)\log n\big)$。 代码常数很大。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #include<cmath> #define db double #define MaxN 500500 using namespace std; namespace io { char buf[5005000],*p1=buf,*p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,5000000,stdin),p1==p2)?EOF:*p1++) int rd() { int x=0;char ch=getchar(),f=0; while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar(); while('0'<=ch&&ch<='9')x=x*10+(ch^48),ch=getchar(); return f?-x:x; } }using io::rd; const db eps=1e-3; struct Point{db x,y;}p[MaxN]; bool cmpP(const Point &A,const Point &B) {return fabs(A.x-B.x)<eps ? A.y<B.y : A.x<B.x;} Point operator + (const Point &A,const Point &B){return (Point){A.x+B.x,A.y+B.y};} Point operator - (const Point &A,const Point &B){return (Point){A.x-B.x,A.y-B.y};} Point operator * (const Point &A,db x){return (Point){A.x*x,A.y*x};} Point operator / (const Point &A,db x){return (Point){A.x/x,A.y/x};} db operator ^ (const Point &A,const Point &B){return A.x*B.y-A.y*B.x;} bool anticlo(Point A,Point B,Point C){return ((A-B)^(C-B))>eps;} db gl(Point A){return sqrt(A.x*A.x+A.y*A.y);} struct Line{Point a,b;}; db dis(Line l,Point p){return ((p-l.a)^(l.b-l.a))/gl(l.b-l.a);} bool chk(Line l,Point p,db r){return dis(l,p)+eps>r;} Point dir(Line l){return (l.b-l.a)/gl(l.b-l.a);} Line shift(Line l,db dis) { Point d=dir(l)*dis; swap(d.x,d.y);d.y*=-1; return (Line){l.a+d,l.b+d}; } Point inter(Line A,Line B) { db sl=(A.a-B.b)^(B.a-B.b),sr=(B.a-B.b)^(A.b-B.b); return A.a+(A.b-A.a)*sl/(sl+sr); } db gr(Line A,Line B,Line C) { Point p1=inter(A,B),p2=inter(B,C); Line l1=(Line){p1,p1-dir(A)+dir(B)} ,l2=(Line){p2,p2-dir(B)+dir(C)}; return fabs(dis(B,inter(l1,l2))); } struct Cir{Point o;int r,p;}s[MaxN]; bool cmpC(const Cir &A,const Cir &B){return A.r<B.r;} int f[MaxN],c[MaxN]; int find(int u) {return f[u]==u ? u : f[u]=find(f[u]);} void merge(int u,int v){ u=find(u);v=find(v); c[f[u]=v]+=c[u]; } Line l[MaxN];db dt[MaxN]; #define Pr pair<db,int> #define fir first #define sec second #define mp make_pair priority_queue<Pr,vector<Pr>,greater<Pr>> q; int nowr,top; void upd(int p) { if (p==1||p==top)return; db ndt=gr(l[find(p-1)],l[p],l[p+c[p]]); if (dt[p]-ndt>eps)q.push(mp(dt[p]=ndt,p)); } void del(int p){ merge(p,p-1);p=find(p); upd(p);upd(p+c[p]); } bool qry(Point p) { int tl=2,tr=top-1; while(tl<tr){ int mid=(tl+tr+1)>>1; int t=find(mid); if (t==1){tl=mid+1;continue;} int pre=find(t-1); if (inter(shift(l[pre],nowr),shift(l[t],nowr)).x<p.x+eps)tl=mid; else tr=mid-1; }return tl<=1||tl>=top||chk(l[find(tl)],p,nowr); } Point stk[MaxN]; int n,m,tn; bool ans[MaxN]; void calc() { top=0; for (int i=1;i<=n;i++){ while(top>1&&!anticlo(stk[top-1],stk[top],p[i]))top--; stk[++top]=p[i]; } top--; for (int i=1;i<=top;i++){ l[i]=(Line){stk[i],stk[i+1]}; f[i]=i;c[i]=1; } while(!q.empty())q.pop(); for (int i=2;i<top;i++) q.push(mp(dt[i]=gr(l[i-1],l[i],l[i+1]),i)); for (int i=1;i<=m;i++){ nowr=s[i].r; while(!q.empty()&&q.top().fir+eps<nowr){ Pr now=q.top();q.pop(); if (now.fir-dt[now.sec]>eps)continue; del(now.sec); } ans[s[i].p]&=chk(l[1],s[i].o,nowr); ans[s[i].p]&=chk(l[top],s[i].o,nowr); if (ans[s[i].p])ans[s[i].p]&=qry(s[i].o); } } void solve() { n=rd(); for (int i=1;i<=n;i++){p[i].x=rd();p[i].y=rd();} sort(p+1,p+n+1,cmpP); m=rd(); for (int i=1;i<=m;i++){ s[i].o.x=rd();s[i].o.y=rd();s[i].r=rd(); ans[s[i].p=i]=1; }sort(s+1,s+m+1,cmpC); calc(); for (int i=1;i<=n;i++)p[i].y*=-1; for (int i=1;i<=m;i++)s[i].o.y*=-1; calc(); for (int i=1;i<=m;i++)putchar(ans[i] ? '1' : '0');puts(""); } int main() { int T=rd(); while(T--)solve(); return 0; } ```