bzoj3630 镜面通道

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

Sample Output

HINT

x<=100000，y<=1000，n<=300

结论：如果最左端与最右端连通，那么就存在一条光路能从最左端到达最右端，就是说水能过去，光就能过去。就是有缝就能过去。(我不会证)

最左端与最右端连通等价于对偶图中上边界与下边界不连通。

如果两个零件有重合部分就连边，跑最小点割集就是答案

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define c(a) memset(a,0,sizeof a)
#define M 610
#define INF (0x7f7f7f7f)
using namespace std;

inline int Readint()
{
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

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;
int cx,cy,k,s,t,n,ans;

inline int min(int x, int y)
{
	if(x < y) return x;
	else return y;
}

inline int abs(int x)
{
	if(x > 0) return x;
	else return -x;
}

inline double dis(int x1,int y1,int x2,int y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) - (1e-10);
}

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;
        
    }
}

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);
}

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()
{
	cx = Readint();
	cy = Readint();
	n = Readint();
	int flow,i,j;
	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 ++)
	{
		a[i].p = Readint();
		if(a[i].p == 1) a[i].x = Readint(), a[i].y = Readint(), a[i].r = Readint();
		else a[i].x1 = Readint(), a[i].y1 = Readint(), a[i].x2 = Readint(), a[i].y2 =Readint();
		for(int 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);
    return 0;
}