测试地址：镜面通道
做法：本题需要用到最小割+计算几何。
首先根据一个神奇的物理学定理：水能通过的地方，光就能通过，所以我们要求的就是AB和CD所属的平面区域连通，继而就是求上边界和下边界不能通过元件连通。因此我们在连通的两个元件之间连边，要求至少要去掉多少个点使得两个点不连通，我们发现这就是一个最小割，然而是对于点的最小割。对此我们把一个点拆成两个点，分为入点和出点，并将所有涉及该点的入边连向入点，将所有涉及该点的出边从出点连出，然后从入点向出点连一条容量为的边。那么割点就变成了割边，原图中所有其他的边容量都设成正无穷的话，最小割中一定不包含原图中的边，那么直接求最小割即可。
这题还有一个难点就是判断两个元件相交/相切，这里讲讲我的做法：
对于矩形和矩形，因为它们都平行于坐标轴，所以我们把它们都投影到两条坐标轴上，并看看它们在坐标轴上的投影是不是都相交，如果都相交的话这两个矩形就是相交的。
对于圆和圆，如果它们圆心间的距离小于等于它们半径的和，那它们就是相交的。
对于矩形和圆，因为本题中互相包含我们也算作相交，所以先判断圆心是不是在矩形内，如果在的话显然相交，否则算出圆心和矩形四边间的最小距离，如果这个最小距离小于等于半径，那么也说明它们相交。
这样我们就做完了这一题。
我傻逼的地方：犯了史上最傻逼的错误之一——数组开小。但是BZOJ和洛谷纷纷显示WA而不是RE，所以我就没仔细看，很是诡异……这种水题都调了我半天啊……
以下是本人代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1000000000;
ll x,y;
int n,S,T,first[610]={0},tot=1;
int h,t,q[610],lvl[610];
struct shape
{
int type;
ll x1,y1,x2,y2,r;
}a[310];
struct edge
{
int v,next,f;
}e[500010];
void insert(int a,int b,int f)
{
e[++tot].v=b;e[tot].next=first[a];e[tot].f=f;first[a]=tot;
e[++tot].v=a;e[tot].next=first[b];e[tot].f=0;first[b]=tot;
}
bool Judge(int x,int y)
{
if (a[x].x1>a[y].x1) swap(x,y);
if (a[x].x2<a[y].x1) return 0;
if (a[x].y1>a[y].y1) swap(x,y);
if (a[x].y2<a[y].y1) return 0;
return 1;
}
ll dis(ll x1,ll y1,ll x2,ll y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
ll calc(ll x,ll y,ll t1,ll t2,ll t3,bool type)
{
if (!type)
{
if (x<=t1) return dis(x,y,t1,t3);
if (x>=t2) return dis(x,y,t2,t3);
return (y-t3)*(y-t3);
}
else
{
if (y<=t1) return dis(x,y,t3,t1);
if (y>=t2) return dis(x,y,t3,t2);
return (x-t3)*(x-t3);
}
}
bool check(int x,int y)
{
if (a[x].type!=2) swap(x,y);
if (a[x].type==2)
{
if (a[y].type==2) return Judge(x,y);
else
{
if (a[y].x1>=a[x].x1&&a[y].x1<=a[x].x2&&a[y].y1>=a[x].y1&&a[y].y1<=a[y].y2) return 1;
if (calc(a[y].x1,a[y].y1,a[x].x1,a[x].x2,a[x].y1,0)<=a[y].r*a[y].r) return 1;
if (calc(a[y].x1,a[y].y1,a[x].x1,a[x].x2,a[x].y2,0)<=a[y].r*a[y].r) return 1;
if (calc(a[y].x1,a[y].y1,a[x].y1,a[x].y2,a[x].x1,1)<=a[y].r*a[y].r) return 1;
if (calc(a[y].x1,a[y].y1,a[x].y1,a[x].y2,a[x].x2,1)<=a[y].r*a[y].r) return 1;
return 0;
}
}
else return dis(a[x].x1,a[x].y1,a[y].x1,a[y].y1)<=(a[x].r+a[y].r)*(a[x].r+a[y].r);
}
void init()
{
scanf("%lld%lld",&x,&y);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].type);
if (a[i].type==1) scanf("%lld%lld%lld",&a[i].x1,&a[i].y1,&a[i].r);
else scanf("%lld%lld%lld%lld",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
}
a[0].type=2,a[0].x1=0,a[0].x2=x,a[0].y1=a[0].y2=y;
a[n+1].type=2,a[n+1].x1=0,a[n+1].x2=x,a[n+1].y1=a[n+1].y2=0;
S=(n<<1)+1,T=(n<<1)+2;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if (check(i,j)) insert(n+i,j,inf),insert(n+j,i,inf);
for(int i=1;i<=n;i++)
{
insert(i,n+i,1);
if (check(0,i)) insert(S,i,inf);
if (check(n+1,i)) insert(n+i,T,inf);
}
}
bool makelevel()
{
for(int i=1;i<=T;i++)
lvl[i]=-1;
h=t=1;
q[1]=S;
lvl[S]=0;
while(h<=t)
{
int v=q[h++];
for(int i=first[v];i;i=e[i].next)
if (e[i].f&&lvl[e[i].v]==-1)
{
lvl[e[i].v]=lvl[v]+1;
q[++t]=e[i].v;
}
}
return lvl[T]!=-1;
}
int maxflow(int v,int maxf)
{
int ret=0,f;
if (v==T) return maxf;
for(int i=first[v];i;i=e[i].next)
if (e[i].f&&lvl[e[i].v]==lvl[v]+1)
{
f=maxflow(e[i].v,min(maxf-ret,e[i].f));
ret+=f;
e[i].f-=f;
e[i^1].f+=f;
if (ret==maxf) return ret;
}
return ret;
}
void dinic()
{
int maxf=0;
while(makelevel())
maxf+=maxflow(S,inf);
printf("%d",maxf);
}
int main()
{
init();
dinic();
return 0;
}