首页 > 代码库 > BZOJ 3630 JLOI2014 镜面通道 计算几何+最小点割集
BZOJ 3630 JLOI2014 镜面通道 计算几何+最小点割集
题目大意:给定一个二维的通道,通道内有一些正方形和圆形的零件(允许重叠),求最少删掉多少零件可以使光线通过反射通过这个通道
看到这题当时我们都吓得说日语了有木有啊!これはいったい何ですか?!計算幾何ですか?圖論ですか?やれますか?全然知らないあああああ!
我在第一第二题上耽误了太长的时间 导致第三题没时间了(第二题还没看到多组数据爆零了 令人感动不已) 最后读入全体数据后加和再加上我的生日然后对n取模+1,零分。。
全场唯一知道正解的写挂了 @Vmurder 写了个枚举射入的坐标横向射入,遇到元件就干掉,拿了50分
最可怕的是有个同样思路,只不过是斜射的怒切了 世界你逗我
这题正解是最小点割集
首先这里有个物理上的费马小定理 具体内容我不知道 但是总之放在这题上就是“水能过去光就能过去”
于是我们还考虑反射什么乱七八糟的搞毛!直接处理圆形和方形,相交就连边,上是源下是汇,求个最小点割集,这题就切了!
确实是道不错的题 只是我的代码写的有点渣 我慢しろ!
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define c(a) memset(a,0,sizeof a) #define M 610 #define INF (0x7fffffff) struct abcde{int p,x,y,r,x1,y1,x2,y2;}a[M>>1]; struct abcd{int to,f,next;}table[200000];int head[M],tot=1; inline void adddd(int x,int y,int z){table[++tot].to=y;table[tot].f=z;table[tot].next=head[x];head[x]=tot;} inline void addd(int x,int y,int z){adddd(x,y,z),adddd(y,x,0);} inline void add(int x,int y){addd(x<<1|1,y<<1,INF),addd(y<<1|1,x<<1,INF);} inline void swap(int&x,int&y){int z=x;x=y;y=z;} inline double dis(int x1,int y1,int x2,int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-(1e-10);} inline int min(int x,int y){return x<y?x:y;} int cx,cy,n,ans,s,t; bool Judge(int x,int y) { int p=a[x].p+a[y].p; if(p==2)return dis(a[x].x,a[x].y,a[y].x,a[y].y)<=a[x].r+a[y].r?1:0; if(p==3) { if(a[x].p==1)swap(x,y); if(dis(a[x].x1,a[x].y1,a[y].x,a[y].y)<=a[y].r)return 1; if(dis(a[x].x1,a[x].y2,a[y].x,a[y].y)<=a[y].r)return 1; if(dis(a[x].x2,a[x].y1,a[y].x,a[y].y)<=a[y].r)return 1; if(dis(a[x].x2,a[x].y2,a[y].x,a[y].y)<=a[y].r)return 1; if(a[x].x2>a[y].x&&a[x].x1<a[y].x)if(abs(a[x].y2-a[y].y)<=a[y].r||abs(a[x].y1-a[y].y)<=a[y].r)return 1; if(a[x].y2>a[y].y&&a[x].y1<a[y].y)if(abs(a[x].x2-a[y].x)<=a[y].r||abs(a[x].x1-a[y].x)<=a[y].r)return 1; if(a[x].x1<=a[y].x&&a[x].x2>=a[y].x&&a[x].y1<=a[y].y&&a[x].y2>=a[y].y)return 1; return 0; } if(p==4) { if((a[x].x1>=a[y].x1&&a[x].x1<=a[y].x2)||(a[x].x2>=a[y].x1&&a[x].x2<=a[y].x2)) if((a[x].y1>=a[y].y1&&a[x].y1<=a[y].y2)||(a[x].y2>=a[y].y1&&a[x].y2<=a[y].y2))return 1; if(a[x].x1<=a[y].x1&&a[y].x2<=a[x].x2&&a[y].y1<=a[x].y1&&a[x].y2<=a[y].y2)return 1; swap(x,y); if((a[x].x1>=a[y].x1&&a[x].x1<=a[y].x2)||(a[x].x2>=a[y].x1&&a[x].x2<=a[y].x2)) if((a[x].y1>=a[y].y1&&a[x].y1<=a[y].y2)||(a[x].y2>=a[y].y1&&a[x].y2<=a[y].y2))return 1; if(a[x].x1<=a[y].x1&&a[y].x2<=a[x].x2&&a[y].y1<=a[x].y1&&a[x].y2<=a[y].y2)return 1; return 0; } } int q[65540],f[M],d[M]; unsigned short r,h; bool bfs() { int i; memset(d,0,sizeof d); h=r;q[++r]=s;d[s]=1; while(h!=r) { h++; for(i=head[q[h]];i;i=table[i].next) if(table[i].f&&!d[table[i].to]) { q[++r]=table[i].to; d[table[i].to]=d[q[h]]+1; if(table[i].to==t)return 1; } } return 0; } int dinic(int x,int flow) { int temp=flow,k,i; if(x==t)return flow; for(i=head[x];i;i=table[i].next) if(table[i].f&&temp&&d[table[i].to]==d[x]+1) { k=dinic(table[i].to,min(temp,table[i].f) ); if(!k)d[table[i].to]=0; table[i].f-=k; table[i^1].f+=k; temp-=k; } return flow-temp; } int main() { int i,j,flow; scanf("%d%d%d",&cx,&cy,&n); s=1;t=n+1<<1; a[0].p=2;a[0].x1=0;a[0].y1=cy;a[0].x2=cx;a[0].y2=cy; a[n+1].p=2;a[n+1].x1=0;a[n+1].y1=0;a[n+1].x2=cx;a[n+1].y2=0; for(i=1;i<=n;i++) { scanf("%d",&a[i].p); if(a[i].p==1)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r); else scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); for(j=0;j<i;j++)if(Judge(i,j))add(i,j); } for(j=1;j<i;j++)if(Judge(j,i))add(j,i); for(i=1;i<=n;i++)adddd(i<<1,i<<1|1,1),adddd(i<<1|1,i<<1,1); while( bfs() ) while( flow=dinic(s,INF) ) ans+=flow; printf("%d",ans); }
BZOJ 3630 JLOI2014 镜面通道 计算几何+最小点割集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。