P1299切孔机（题解）
Link.
PS:
人生中的第一道黑题。（可惜现在掉绿了）
发一个题解纪念一下。
Solution.
首先先把读入的$\texttt{x},\texttt{y}$离散化
把所有的切痕记录下来
bfs把孔外的格子找出来
数有几个格子。（一个图中有几个连通块）
My Coding.
- xx,yy:表示方向。
- point:表示点。
- number:第几次切
- x,y:切的点的坐标
- picture:记录切痕
- can_go:一个点可以不可以向上下左右走(0:上,1:下,2:左:右)
- visit:一个点是不是孔中的点(0:不是,1:是)
- cmpx,cmpy:离散化时用
- cmp:切的次数从小到大，第一个切点尽量左上
- ready:读入
- lisan:离散化
- build_wall:把所有切痕记录下来（2）
- cut_paper:剪纸，把孔外的格子记录下来（3）
- count_hole:数有几个洞（4）
Coding.
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
using namespace std;
typedef long long ll;
const ll xx[4]={-1,1,0,0},yy[4]={0,0,-1,1};
struct point
{
ll number,x,y;
point() {}
point(ll a,ll b):x(a),y(b) {}
};
struct picture
{
bool can_go[4],visit;
picture()
{
can_go[0]=can_go[1]=can_go[2]=can_go[3]=1;
visit=1;
}
};
ll n;
point a[205];
picture b[205][205];
inline bool cmpx(point a,point b)
{
return a.x<b.x;
}
inline bool cmpy(point a,point b)
{
return a.y<b.y;
}
inline bool cmp(point a,point b)
{
if(a.number!=b.number) return a.number<b.number;
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
inline void ready()
{
scanf("%lld",&n);
for(int i=1;i<=n*2;i++)
{
a[i].number=(i+1)/2;
scanf("%lld%lld",&a[i].x,&a[i].y);
}
}
inline void lisan()
{
ll now,u;
now=-10000005;
u=0;
sort(a+1,a+n*2+1,cmpx);
for(ll i=1;i<=n*2;i++)
{
if(a[i].x!=now)
{
now=a[i].x;
u++;
a[i].x=u;
}
else a[i].x=u;
}
now=-10000005;
u=0;
sort(a+1,a+n*2+1,cmpy);
for(ll i=1;i<=n*2;i++)
{
if(a[i].y!=now)
{
now=a[i].y;
u++;
a[i].y=u;
}
else a[i].y=u;
}
}
inline void build_wall()
{
sort(a+1,a+n*2+1,cmp);
for(ll i=1;i<=n;i++)
{
point s=a[i*2-1],e=a[i*2];
for(ll j=s.x+1;j<=e.x;j++)
{
b[j][s.y].can_go[3]=0;
b[j][s.y+1].can_go[2]=0;
}
for(ll j=s.y+1;j<=e.y;j++)
{
b[s.x][j].can_go[1]=0;
b[s.x+1][j].can_go[0]=0;
}
}
}
inline void cut_paper()
{
queue<point>q;
q.push(point(0,0));
while(!q.empty())
{
point now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
ll x=now.x+xx[i],y=now.y+yy[i];
if(x<0||x>200||y<0||y>200) continue;
if(!b[x][y].visit) continue;
if(!b[now.x][now.y].can_go[i]) continue;
b[x][y].visit=0;
q.push(point(x,y));
}
}
}
inline void bfs(ll dx,ll dy)
{
queue<point>q;
b[dx][dy].visit=0;
q.push(point(dx,dy));
while(!q.empty())
{
point now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
ll x=now.x+xx[i],y=now.y+yy[i];
if(x<0||x>200||y<0||y>200) continue;
if(!b[x][y].visit) continue;
b[x][y].visit=0;
q.push(point(x,y));
}
}
}
inline ll count_hole()
{
ll ans=0;
for(ll i=0;i<=200;i++)
for(ll j=0;j<=200;j++)
{
if(!b[i][j].visit) continue;
ans++;
bfs(i,j);
}
return ans;
}
int main()
{
ready();
lisan();
build_wall();
cut_paper();
ll ans=count_hole();
printf("%lld\n",ans);
return 0;
}