题目大意
在一个二维平面内，给出一个镜面通道和若干个镜面元件，每个元件可能是圆形或矩形。求出为了能够使光从通道左边通过通道到达右边，至少需要拿走的元件个数。
思路分析
首先，存在一个结论：如果通道中存在从左边到右边的路径，那么光就能通过。
证明一下：当通道中存在从左边到右边的路径时，我们不妨将通道竖直放置，令左边朝上，向通道中注水，那么水一定能从下方流出。考虑水恰好流出时，即流出的水形成“水线”时，将通道的剩余部分填满，那么光一定可以沿顺着水的方向通过，所以在剩余部分没有填满的情况下光也能通过。
那么现在的问题就变成了，至少需要拿走多少元件可以使得通道中存在从左到右的路径，而这等价于通道的上下边界无法通过元件连通。
我们发现，上下边界的连通性与元件的形状，大小均无关，只与元件之间是否接触有关。那么我们可以将元件抽象成点，点与点之间存在边当且仅当两个点代表的元件接触，这样就形成了一张图。
我们同时也可以将上下边界抽象成点加入图，连边方式与元件类似，即如果存在元件与边界相接触，那么将该元件代表的点和边界代表的点连边。
那么问题就转化为了，至少需要删除多少个点，可以使得上下边界代表的两点不连通。
这显然是一个最小割问题，可以通过网络流解决。
建图方式比较简单，将点拆成入点和出点，出入点之间连边权为 \(1\) 的边，将上下边界代表的点设为源点和汇点，点与点之间，点与边界之间连边权为 \(+\infty\) 的边即可。
现在考虑如何判断两个元件之间接触：
- 圆和圆
直接计算两圆心的距离是否小于等于半径之和即可。
- 矩形和矩形
枚举两个矩形的四个顶点是否在另一矩形内即可？
考虑如下情况：
因此还需逐一判断边是否相交。
- 圆和矩形
可以转化成点是否在一个圆角矩形内，将圆角矩形拆成四个圆和两个矩形，将点视为半径为 \(0\) 的圆用上面的方法做即可。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int M=330,N=220000;
#define eps 1e-6
#define inf 0x3f3f3f3f
int n,S,T,idx=1,op;
double in1,in2,in3,in4,cx,cy;
int to[N],nxt[N],head[N],w[N];
int cur[N],d[N];
void add(int u,int v,int c){
idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;w[idx]=c;
idx++;to[idx]=u;nxt[idx]=head[v];head[v]=idx;w[idx]=0;
}
queue <int> q;
bool bfs(){
memset(d,-1,sizeof d);
while(!q.empty()) q.pop();
cur[S]=head[S];
q.push(S);d[S]=0;
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head[now];i;i=nxt[i]){
int v=to[i];
if(~d[v]||!w[i]) continue;
d[v]=d[now]+1;
cur[v]=head[v];
if(v==T) return 1;
q.push(v);
}
}
return 0;
}
int dfs(int s,int lim){
if(s==T) return lim;
int flow=0;
for(int i=cur[s];i&&flow<lim;i=nxt[i]){
int v=to[i];cur[s]=i;
if(d[v]!=d[s]+1||!w[i]) continue;
int t=dfs(v,min(w[i],lim-flow));
if(!t) d[v]=-1;
w[i]-=t;w[i^1]+=t;flow+=t;
}
return flow;
}
int dinic(){//dinic 板子
int ans=0,flow=0;
while(bfs()) while(flow=dfs(S,inf)) ans+=flow;
return ans;
}
struct Node{
int type;//1代表圆，2代表矩形，3表示线段
double x1,y1,x2,y2,r;
}a[M];
double dis_two_points(double x1,double y1,double x2,double y2){//计算两点距离
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool Point_Rec(double x1,double y1,Node a){//判断点是否在矩形内
return (x1>a.x1-eps)&&(x1<a.x2+eps)&&(y1>a.y1-eps)&&(y1<a.y2+eps);
}
bool Lin_Int(Node a,Node b){//判断特定直线是否相交
return (a.x1<=b.x1&&b.x1<=a.x2)&&(b.y1<=a.y1&&a.y1<=b.y2);
}
bool Cyc_Int(Node a,Node b){//判断圆是否相交
return dis_two_points(a.x1,a.y1,b.x1,b.y1)<a.r+b.r+eps;
}
bool Rec_Int(Node a,Node b){//判断两个矩形是否相交
bool res1=Point_Rec(a.x1,a.y1,b);
bool res2=Point_Rec(a.x2,a.y2,b);
bool res3=Point_Rec(a.x1,a.y2,b);
bool res4=Point_Rec(a.x2,a.y1,b);//判点
Node line1=Node{3,a.x1,a.y1,a.x2,a.y1};
Node line2=Node{3,a.x1,a.y1,a.x1,a.y2};
Node line3=Node{3,a.x2,a.y1,a.x2,a.y2};
Node line4=Node{3,a.x1,a.y2,a.x2,a.y2};
Node line5=Node{3,b.x1,b.y1,b.x2,b.y1};
Node line6=Node{3,b.x1,b.y1,b.x1,b.y2};
Node line7=Node{3,b.x2,b.y1,b.x2,b.y2};
Node line8=Node{3,b.x1,b.y2,b.x2,b.y2};//两个矩形八条线
bool res5=Lin_Int(line1,line6)||Lin_Int(line1,line7);
bool res6=Lin_Int(line2,line5)||Lin_Int(line2,line8);
bool res7=Lin_Int(line3,line5)||Lin_Int(line3,line8);
bool res8=Lin_Int(line4,line6)||Lin_Int(line4,line8);//线是否相交
return res1||res2||res3||res4||res5||res6||res7||res8;
}
bool check(Node a,Node b){
if(a.type==1&&b.type==1) return Cyc_Int(a,b);
if(a.type==2&&b.type==2) return Rec_Int(a,b)||Rec_Int(b,a);//考虑一个矩形在另一个矩形内的情况
if(a.type!=b.type){
if(a.type==2) swap(a,b);
Node point=Node{1,a.x1,a.y1,0,0,0};
bool res1=Cyc_Int(point,Node{1,b.x1,b.y1,0,0,a.r});
bool res2=Cyc_Int(point,Node{1,b.x2,b.y2,0,0,a.r});
bool res3=Cyc_Int(point,Node{1,b.x1,b.y2,0,0,a.r});
bool res4=Cyc_Int(point,Node{1,b.x2,b.y1,0,0,a.r});//视为四个圆和两个矩形
bool res5=Point_Rec(a.x1,a.y1,Node{2,b.x1-a.r,b.y1,b.x2+a.r,b.y2});
bool res6=Point_Rec(a.x1,a.y1,Node{2,b.x1,b.y1-a.r,b.x2,b.y2+a.r});
return res1||res2||res3||res4||res5||res6;
}
return 0;
}
int main(){
scanf("%lf%lf%d",&cx,&cy,&n);
for(int i=1;i<=n;i++){
scanf("%d%lf%lf%lf",&op,&in1,&in2,&in3);
if(op==2) scanf("%lf",&in4);
if(op==1) a[i]=Node{1,in1,in2,0,0,in3};
if(op==2) a[i]=Node{2,in1,in2,in3,in4};
}
S=N-5;T=N-6;
a[n+1]=Node{2,-inf,cy,inf,inf};//上下边界可以当作两个无穷大的矩形
a[n+2]=Node{2,-inf,-inf,inf,0};
for(int i=1;i<=n;i++){
if(check(a[n+1],a[i])) add(S,2*i-1,inf);
if(check(a[n+2],a[i])) add(2*i,T,inf);
add(2*i-1,2*i,1);//入点和出点
for(int j=i+1;j<=n;j++)//暴力加边即可
if(check(a[i],a[j])){
add(2*i,2*j-1,inf);
add(2*j,2*i-1,inf);
}
}
cout<<dinic()<<'\n';
return 0;
}