1 条题解

  • 1
    @ 2022-8-17 22:04:07
    #include<bits/stdc++.h>
    using namespace std;const double eps=1e-7;const int INF=1e9;
    struct rnd{double x,y,r;int id;}a[1205];
    struct squ{double x1,y1,x2,y2;int id;}b[1205];
    struct edge{int to,w,nxt;}e[2000005];
    double Cx,Cy;int n,et,s,t,head[1205],d[1205],cr[1205],ac,bc;
    inline char chk(squ a,double x,double y) {return a.x1-eps<=x&&x<=a.x2+eps&&a.y1-eps<=y&&y<=a.y2+eps;}
    inline char CHK(squ a,double y,double x1,double x2) {return (a.y1-eps<=y&&y<=a.y2+eps)||chk(a,x1,y)||chk(a,x2,y);}
    inline char chk1(rnd a,double x,double y1,double y2)
    {
    	if((a.x-x)*(a.x-x)+(a.y-y1)*(a.y-y1)<=a.r*a.r+eps) return 1;
    	if((a.x-x)*(a.x-x)+(a.y-y2)*(a.y-y2)<=a.r*a.r+eps) return 1;
    	if(!(a.x-x<=a.r+eps&&a.x-x>=a.r-eps)) return 0;
    	double dy=sqrt(a.r*a.r-(a.x-x)*(a.x-x)),Y1=a.y-dy,Y2=a.y+dy;
    	return (y1-eps<=Y1&&Y1<=y2+eps)||(y1-eps<=Y2&&Y2<=y2+eps);
    }
    inline char chk2(rnd a,double y,double x1,double x2)
    {
    	if((a.x-x1)*(a.x-x1)+(a.y-y)*(a.y-y)<=a.r*a.r+eps) return 1;
    	if((a.x-x2)*(a.x-x2)+(a.y-y)*(a.y-y)<=a.r*a.r+eps) return 1;
    	if(!(a.y-y<=a.r+eps&&a.y-y>=-a.r-eps)) return 0;
    	double dx=sqrt(a.r*a.r-(a.y-y)*(a.y-y)),X1=a.x-dx,X2=a.x+dx;
    	return (x1-eps<=X1&&X1<=x2+eps)||(x1-eps<=X2&&X2<=x2+eps);
    }
    inline char operator+(rnd a,rnd b) {return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)<=(a.r+b.r+eps)*(a.r+b.r+eps);}
    inline char operator+(squ a,squ b) {return chk(a,b.x1,b.y1)||chk(a,b.x1,b.y2)||chk(a,b.x2,b.y1)||chk(a,b.x2,b.y2);}
    inline char operator+(squ a,rnd b)
    {
    	if((a.x1-b.x)*(a.x1-b.x)+(a.y1-b.y)*(a.y1-b.y)<=b.r*b.r+eps) return 1;
    	if((a.x2-b.x)*(a.x2-b.x)+(a.y1-b.y)*(a.y1-b.y)<=b.r*b.r+eps) return 1;
    	if((a.x1-b.x)*(a.x1-b.x)+(a.y2-b.y)*(a.y2-b.y)<=b.r*b.r+eps) return 1;
    	if((a.x2-b.x)*(a.x2-b.x)+(a.y2-b.y)*(a.y2-b.y)<=b.r*b.r+eps) return 1;
    	if(chk(a,b.x,b.y)) return 1;
    	if(chk1(b,a.x1,a.y1,a.y2)||chk1(b,a.x2,a.y2,a.y2)||chk2(b,a.y1,a.x1,a.x2)||chk2(b,a.y2,a.x1,a.x2)) return 1;
    	return 0;
    }
    inline void ADDE(int x,int y,int w) {e[++et]=(edge){y,w,head[x]},head[x]=et;}
    inline void adde(int x,int y,int w) {ADDE(x,y,w),ADDE(y,x,0);}
    inline char bfs(int s,int t)
    {
    	queue<int>q;q.push(s),memset(d,0,sizeof(d)),d[s]=1;
    	while(!q.empty())
    	{
    		int x=q.front();q.pop();
    		for(int i=head[x];i;i=e[i].nxt) if(e[i].w&&!d[e[i].to]) d[e[i].to]=d[x]+1,q.push(e[i].to);
    	}
    	return !!d[t];
    }
    #define rev(x) ((((x)&1)?1:-1)+(x))
    inline int dfs(int x,int t,int lim=INF)
    {
    	int f=lim;if(x==t) return lim;
    	for(int i=cr[x];i;cr[x]=i=e[i].nxt) if(d[e[i].to]==d[x]+1&&e[i].w)
    	{
    		int g=dfs(e[i].to,t,min(f,e[i].w));f-=g;
    		e[i].w-=g,e[rev(i)].w+=g;if(!f) break;
    	}
    	return lim-f;
    }
    inline int dinic(int s,int t) {int r=0;while(bfs(s,t)) memcpy(cr,head,sizeof(cr)),r+=dfs(s,t);return r;}
    int main()
    {
    	scanf("%lf%lf%d",&Cx,&Cy,&n),et=0,memset(head,0,sizeof(head)),s=n<<1|1,t=s+1;
    	for(int i=1,fg;i<=n;i++)
    	{
    		scanf("%d",&fg);if(fg^2) ++ac,scanf("%lf%lf%lf",&a[ac].x,&a[ac].y,&a[ac].r),a[ac].id=i;
    		else bc++,scanf("%lf%lf%lf%lf",&b[bc].x1,&b[bc].y1,&b[bc].x2,&b[bc].y2),b[bc].id=i;
    	}
    	for(int i=1;i<=n;i++) adde(i,i+n,1);
    	for(int i=1;i<=ac;i++) if(chk2(a[i],0,0,Cx)) adde(s,a[i].id,1);
    	for(int i=1;i<=bc;i++) if(CHK(b[i],0,0,Cx)) adde(s,b[i].id,1);
    	for(int i=1;i<=ac;i++) if(chk2(a[i],Cy,0,Cx)) adde(a[i].id+n,t,1);
    	for(int i=1;i<=bc;i++) if(CHK(b[i],Cy,0,Cx)) adde(b[i].id+n,t,1);
    	for(int i=1;i<=ac;i++) for(int j=1;j<=ac;j++) if(i!=j&&a[i]+a[j]) adde(a[i].id+n,a[j].id,1);
    	for(int i=1;i<=bc;i++) for(int j=1;j<=ac;j++) if(i!=j&&b[i]+a[j]) adde(b[i].id+n,a[j].id,1);
    	for(int i=1;i<=ac;i++) for(int j=1;j<=bc;j++) if(i!=j&&b[j]+a[i]) adde(a[i].id+n,b[j].id,1);
    	for(int i=1;i<=bc;i++) for(int j=1;j<=bc;j++) if(i!=j&&(b[i]+b[j]||b[j]+b[i])) adde(b[i].id+n,b[j].id,1);
    	return printf("%d\n",dinic(s,t)),0;
    }
    
    • 1

    信息

    ID
    239
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    3
    上传者