【BZOJ3630】[JLOI2014]镜面通道
Description
在一个二维平面上，有一个镜面通道，由镜面AC，BD组成，AC，BD长度相等，且都平行于x轴，B位于（0，0）。通道中有n个外表面为镜面的光学元件，光学元件α为圆形，光学元件β为矩形（这些元件可以与其他元件和通道有交集，具体看下图）。光线可以在AB上任一点以任意角度射入通道，光线不会发生削弱。当出现元件与元件，元件和通道刚好接触的情况视为光线无法透过（比如两圆相切）。现在给出通道中所有元件的信息（α元件包括圆心坐标和半径xi，yi，ri，β元件包括左下角和右上角坐标x1，y1，x2，y2）
如上图，S到T便是一条合法线路。
当然，显然存在光线无法透过的情况，现在交给你一个艰巨的任务，请求出至少拿走多少个光学元件后，存在一条光线线路可以从CD射出。
下面举例说明：
现在假设，取走中间那个矩形，那么就可以构造出一条穿过通道的光路，如图中的S到T。
Input
第一行包含两个整数，x，y，表示C点坐标
第二行包含一个数字，n，表示有n个光学元件
接下来n行
第一个数字如果是1，表示元件α，后面会有三个整数xi，yi，ri分别表示圆心坐标和半径
第一个数字如果是2，表示元件β，后面会有四个整数x1，y1，x2，y2分别表示左下角和右上角坐标（矩形都平行，垂直于坐标轴）
Output
输出包含一行，至少需要拿走的光学元件个数m
Sample Input
1000 100
6
1 500 0 50
2 10 10 20 100
2 100 10 200 100
2 300 10 400 100
2 500 10 600 100
2 700 0 800 100
6
1 500 0 50
2 10 10 20 100
2 100 10 200 100
2 300 10 400 100
2 500 10 600 100
2 700 0 800 100
Sample Output
2
HINT
x<=100000，y<=1000，n<=300
题解：首先，有一个神奇的物理结论：水能通过的地方光就能通过。（本人物理渣~）
然后水能通过的条件是整个通道不被堵死，即在对偶图中，上界和下界不连通。于是最小割判定即可。
写了一大坨代码，自己都不敢调了，不过这题数据还真是水，居然1A了~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const double eps=1e-10;
double X,Y;
int n,nr,nc,S,T,cnt,ans;
int to[400000],next[400000],val[400000],head[1000],d[1000];
queue<int> q;
struct rectangle
{
double x1,y1,x2,y2;
bool inside(double x,double y)
{
return x>=x1&&x<=x2&&y>=y1&&y<=y2;
}
}pr[310];
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
struct circle
{
double x,y,r;
bool inside(double a,double b)
{
return dis(a,b,x,y)<=r+eps;
}
bool xcross(double x1,double x2,double y1)
{
double len=sqrt(r*r-(y-y1)*(y-y1));
if((x+len>=x1&&x+len<=x2)||(x-len>=x1&&x-len<=x2)) return 1;
return 0;
}
bool ycross(double x1,double y1,double y2)
{
double len=sqrt(r*r-(x-x1)*(x-x1));
if((y+len>=y1&&y+len<=y2)||(y-len>=y1&&y-len<=y2)) return 1;
return 0;
}
}pc[310];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
to[cnt]=a,val[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
int dfs(int x,int mf)
{
if(x==T) return mf;
int i,temp=mf,k;
for(i=head[x];i!=-1;i=next[i])
{
if(d[to[i]]==d[x]+1&&val[i])
{
k=dfs(to[i],min(temp,val[i]));
if(!k) d[to[i]]=0;
val[i]-=k,val[i^1]+=k,temp-=k;
if(!temp) break;
}
}
return mf-temp;
}
int bfs()
{
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
int i,u;
q.push(S),d[S]=1;
while(!q.empty())
{
u=q.front(),q.pop();
for(i=head[u];i!=-1;i=next[i])
{
if(!d[to[i]]&&val[i])
{
d[to[i]]=d[u]+1;
if(to[i]==T) return 1;
q.push(to[i]);
}
}
}
return 0;
}
int main()
{
X=rd(),Y=rd(),n=rd();
S=2*n+1,T=2*n+2;
int i,j;
memset(head,-1,sizeof(head));
for(i=1;i<=n;i++)
{
if(rd()==1) pc[++nc].x=rd(),pc[nc].y=rd(),pc[nc].r=rd();
else pr[++nr].x1=rd(),pr[nr].y1=rd(),pr[nr].x2=rd(),pr[nr].y2=rd();
}
for(i=1;i<=nr;i++)
{
for(j=i+1;j<=nr;j++)
{
if(pr[j].inside(pr[i].x1,pr[i].y1)||pr[j].inside(pr[i].x1,pr[i].y2)||pr[j].inside(pr[i].x2,pr[i].y1)||pr[j].inside(pr[i].x2,pr[i].y2)
||pr[i].inside(pr[j].x1,pr[j].y1)||pr[i].inside(pr[j].x1,pr[j].y2)||pr[i].inside(pr[j].x2,pr[j].y1)||pr[i].inside(pr[j].x2,pr[j].y2)
||(pr[i].x1<=pr[j].x1&&pr[j].x2<=pr[i].x2&&pr[j].y1<=pr[i].y1&&pr[i].y2<=pr[j].y2)
||(pr[j].x1<=pr[i].x1&&pr[i].x2<=pr[j].x2&&pr[i].y1<=pr[j].y1&&pr[j].y2<=pr[i].y2)) add(i+n,j,1<<30),add(j+n,i,1<<30);
}
}
for(i=1;i<=nc;i++)
for(j=i+1;j<=nc;j++)
if(dis(pc[i].x,pc[i].y,pc[j].x,pc[j].y)<=pc[i].r+pc[j].r) add(i+n+nr,j+nr,1<<30),add(j+nr+n,i+nr,1<<30);
for(i=1;i<=nr;i++)
{
for(j=1;j<=nc;j++)
{
if(pr[i].inside(pc[j].x,pc[j].y)||pc[j].inside(pr[i].x1,pr[i].y1)||pc[j].inside(pr[i].x1,pr[i].y2)||pc[j].inside(pr[i].x2,pr[i].y1)||pc[j].inside(pr[i].x2,pr[i].y2)
||pc[j].xcross(pr[i].x1,pr[i].x2,pr[i].y1)||pc[j].xcross(pr[i].x1,pr[i].x2,pr[i].y2)
||pc[j].ycross(pr[i].x1,pr[i].y1,pr[i].y2)||pc[j].ycross(pr[i].x2,pr[i].y1,pr[i].y2))
add(i+n,j+nr,1<<30),add(j+n+nr,i,1<<30);
}
}
for(i=1;i<=nr;i++)
{
add(i,i+n,1);
if(pr[i].y2>=Y) add(S,i,1<<30);
if(pr[i].y1<=0) add(i+n,T,1<<30);
}
for(i=1;i<=nc;i++)
{
add(i+nr,i+nr+n,1);
if(pc[i].y+pc[i].r>=Y) add(S,i+nr,1<<30);
if(pc[i].y-pc[i].r<=0) add(i+nr+n,T,1<<30);
}
while(bfs()) ans+=dfs(S,1<<30);
printf("%d",ans);
return 0;
}