JLOI2014 镜面通道（计算几何+网络流）

发表于 |
字数统计: 1,483字 | 阅读时长 ≈ 8min

【JLOI2014】镜面通道

问题描述

在一个二维平面上，有一个镜面通道，由镜面AC，BD组成，AC，BD长度相等，且都平行于x轴，B位于（0，0）。通道中有n个外表面为镜面的光学元件，光学元件α为圆形，光学元件β为矩形（这些元件可以与其他元件和通道有交集，具体看下图）。光线可以在AB上任一点以任意角度射入通道，光线不会发生削弱。当出现元件与元件，元件和通道刚好接触的情况视为光线无法透过（比如两圆相切）。现在给出通道中所有元件的信息（α元件包括圆心坐标和半径xi，yi，ri，β元件包括左下角和右上角坐标x1，y1，x2，y2）

.jpg.gif)

如上图，S到T便是一条合法线路。

.jpg.gif)

当然，显然存在光线无法透过的情况，现在交给你一个艰巨的任务，请求出至少拿走多少个光学元件后，存在一条光线线路可以从CD射出。

下面举例说明：

现在假设，取走中间那个矩形，那么就可以构造出一条穿过通道的光路，如图中的S到T。

输入格式

第一行包含两个整数，x，y，表示C点坐标

第二行包含一个数字，n，表示有n个光学元件

接下来n行

第一个数字如果是1，表示元件α，后面会有三个整数xi，yi，ri分别表示圆心坐标和半径

第一个数字如果是2，表示元件β，后面会有四个整数x1，y1，x2，y2分别表示左下角和右上角坐标（矩形都平行，垂直于坐标轴）

输出格式

输出包含一行，至少需要拿走的光学元件个数m

样例输入

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

样例输出

2

提示

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

首先，你需要知道一些物理知识。根据神奇的反射定律，那么只要上下两块板之间还有空隙，那么光线一定可以穿过去。

也就是说光线无法透过当且仅当由圆和矩形构成了一条连接上下两板的通路。

那么这题就比较显然了，相交的元件连边，每个元件拆点限制用的次数，然后跑一个最小割就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
#define ll long long
using namespace std;
struct node{int x,y,r,id;}C[N];
struct nodd{int x1,y1,x2,y2,id;}D[N];
int X,Y,n,tot1,tot2,S,T;
int TOT=1,LA[N],NE[N],EN[N],G[N],La[N];
int Dis[N],cnt[N],ans;
void ADD(int x,int y,int z)
{
	TOT++;
	G[TOT]=z;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=La[x]=TOT;
}
void Link(int x,int y,int z)
{
	ADD(x,y,z);
	ADD(y,x,0);
}
ll dis(int x1,int y1,int x2,int y2)
{
	ll x=x1-x2,y=y1-y2;
	return x*x+y*y;
}
bool Cross1(int i,int j)
{
	ll d=C[i].r+C[j].r;
	return d*d>=dis(C[i].x,C[i].y,C[j].x,C[j].y);
}
bool Cross2(int i,int j)
{
	ll d=1ll*C[i].r*C[i].r;
	if(dis(D[j].x1,D[j].y1,C[i].x,C[i].y)<=d)return 1;
	if(dis(D[j].x1,D[j].y2,C[i].x,C[i].y)<=d)return 1;
	if(dis(D[j].x2,D[j].y1,C[i].x,C[i].y)<=d)return 1;
	if(dis(D[j].x2,D[j].y2,C[i].x,C[i].y)<=d)return 1;
	if(C[i].y<=D[j].y2&&C[i].y>=D[j].y1)
	{
		if(C[i].x>=D[j].x1&&C[i].x<=D[j].x2)return 1;
		if(max(C[i].x-D[j].x2,D[j].x1-C[i].x)<=C[i].r)return 1;
	}
	if(C[i].x>=D[j].x1&&C[i].x<=D[j].x2)
	{
		if(C[i].y>=D[j].y1&&C[i].y<=D[j].y2)return 1;
		if(max(C[i].y-D[j].y2,D[j].y1-C[i].y)<=C[i].r)return 1;
	}
	return 0;
}
bool Cross3(int i,int j)
{
	if(D[i].x2<D[j].x1)return 0;
	if(D[i].x1>D[j].x2)return 0;
	if(D[i].y1>D[j].y2)return 0;
	if(D[i].y2<D[j].y1)return 0;
	return 1;
}
int SAP(int x,int f)
{
	if(x==T)return f;
	int i,y,tmp,d=0;
	for(i=LA[x];i;i=LA[x]=NE[i])
	{
		y=EN[i];
		if(!G[i]||Dis[x]!=Dis[y]+1)continue;
		tmp=SAP(y,min(f-d,G[i]));
		d+=tmp;G[i]-=tmp;G[i^1]+=tmp;
		if(d==f||Dis[S]>T)return LA[x]=La[x],d;
	}
	if(!--cnt[Dis[x]])Dis[S]=T+1;
	cnt[++Dis[x]]++;
	return LA[x]=La[x],d;
}
int main()
{
	int i,j,k,x,y,z,p,q;
	scanf("%d%d%d",&X,&Y,&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%d%d%d",&x,&y,&z);
			C[++tot1]=(node){x,y,z,i};
		}
		else
		{
			scanf("%d%d%d%d",&x,&y,&p,&q);
			D[++tot2]=(nodd){x,y,p,q,i};
		}
	}
	S=n+n+1;T=S+1;
	for(i=1;i<=tot1;i++)
	{
		if(C[i].y<=C[i].r)Link(S,C[i].id,1);
		if(C[i].y+C[i].r>=Y)Link(C[i].id+n,T,1);
	}
	for(i=1;i<=tot2;i++)
	{
		if(D[i].y1<=0)Link(S,D[i].id,1);
		if(D[i].y2>=Y)Link(D[i].id+n,T,1);
	}
	for(i=1;i<=tot1;i++)
	{
		for(j=1;j<=tot1;j++)if(i!=j&&Cross1(i,j))Link(C[i].id+n,C[j].id,1);
		for(j=1;j<=tot2;j++)if(Cross2(i,j))Link(C[i].id+n,D[j].id,1);
	}
	for(i=1;i<=tot2;i++)
	{
		for(j=1;j<=tot2;j++)if(i!=j&&Cross3(i,j))Link(D[i].id+n,D[j].id,1);
		for(j=1;j<=tot1;j++)if(Cross2(j,i))Link(D[i].id+n,C[j].id,1);
	}
	for(i=1;i<=n;i++)Link(i,i+n,1);
	while(Dis[S]<=T)ans+=SAP(S,1e9);
	printf("%d",ans);
}