ZOJ :: Problems :: Show Problem
这题是从校内oj的几何分类里面找到的。
题意不难，就是给出一个区域(L,W)，这个区域里面有很多多边形，多边形的边都是和x/y轴平行的。一个射线源在(L,0)，射线是走平行于x/y轴的路径的。它们可以贴着多边形的边经过，不过不能穿过区域中的多边形，甚至不能从有至少一个交点的两条边之间穿过（区域边沿也一样）。射线只能向着x减少或者y增大的方向行走，问有多大的区域是没有射线经过的，不包括多边形区域。
做法就是，先将区域离散化成若干矩形，然后将每一个矩形看成一个点，构出图以后bfs射线就可以了。最后统计没有射线经过的区域大小即可。
做的时候注意，数组大小要控制好。如果射线源的位置在开始的时候就被覆盖了，可以直接计算没有多边形覆盖的面积。
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map> using namespace std; const int N = ;
const int M = N * N;
map<int, int> xid, yid;
bool blx[M >> ][M >> ], vis[M >> ][M >> ];
typedef long long LL;
typedef pair<int, int> PII; int L, W;
int rx[M], ry[M], xn, yn, pn[N];
PII poly[N][N]; void fix(int id) {
int mk = ;
for (int i = ; i < pn[id]; i++) if (poly[id][mk] < poly[id][i]) mk = i;
rotate(poly[id], poly[id] + mk, poly[id] + pn[id]);
} const int dx[] = { -, -, , , };
const int dy[] = { , , , , -}; inline LL cross(PII a, PII b) { return (LL) a.first * b.second - (LL) a.second * b.first;}
PII operator - (PII a, PII b) { return PII(a.first - b.first, a.second - b.second);} bool inPoly(PII pt, int id) {
int wn = ;
poly[id][pn[id]] = poly[id][];
for (int i = ; i < pn[id]; i++) {
LL k = cross(poly[id][i + ] - poly[id][i], pt - poly[id][i]);
int d1 = poly[id][i].second - pt.second;
int d2 = poly[id][i + ].second - pt.second;
if (k > && d1 <= && d2 > ) wn++;
if (k < && d2 <= && d1 > ) wn--;
}
return wn != ;
} int qx[M * M >> ], qy[M * M >> ];
inline bool inMat(int x, int y) { return <= x && x < xn && <= y && y < yn;} void fill(int id) {
int cx = xid[poly[id][].first] - ;
int cy = yid[poly[id][].second] - ;
blx[cx][cy] = true;
int qh, qt, nx, ny;
qh = qt = ;
qx[qt] = cx, qy[qt++] = cy;
while (qh < qt) {
cx = qx[qh], cy = qy[qh++];
for (int i = ; i < ; i++) {
nx = cx + dx[i], ny = cy + dy[i];
if (inMat(nx, ny) && !blx[nx][ny] && inPoly(PII(rx[nx] + rx[nx + ] >> , ry[ny] + ry[ny + ] >> ), id)) {
blx[nx][ny] = true;
qx[qt] = nx, qy[qt++] = ny;
}
}
}
} LL work(int n) {
int cx = xn - , cy = ;
LL sum = ;
int qh, qt, nx, ny;
memset(vis, , sizeof(vis));
qh = qt = ;
if (!blx[cx][cy]) {
qx[qt] = cx, qy[qt++] = cy;
vis[cx][cy] = true;
}
while (qh < qt) {
cx = qx[qh], cy = qy[qh++];
for (int i = ; i < ; i++) {
nx = cx + dx[i], ny = cy + dy[i];
if (inMat(nx, ny) && !blx[nx][ny] && !vis[nx][ny]) {
vis[nx][ny] = true;
qx[qt] = nx, qy[qt++] = ny;
}
}
}
for (int i = ; i < xn; i++) {
for (int j = ; j < yn; j++) {
if (vis[i][j] || blx[i][j]) continue;
sum += (LL) (rx[i + ] - rx[i]) * (ry[j + ] - ry[j]);
}
}
// for (int j = 0; j < yn; j++) {
// for (int i = 0; i < xn; i++) printf("%d", !vis[i][j] && !blx[i][j]);
// puts("");
// }
// cout << "sum " << sum << endl;
return sum >> ;
} void PRE(int n) {
sort(rx, rx + xn);
xn = unique(rx, rx + xn) - rx;
xid.clear();
for (int i = ; i < xn; i++) xid[rx[i]] = i;
sort(ry, ry + yn);
yn = unique(ry, ry + yn) - ry;
yid.clear();
for (int i = ; i < yn; i++) yid[ry[i]] = i;
xn--, yn--;
// for (int i = 0; i < xn; i++) cout << i << '~' << rx[i] << endl;
// for (int i = 0; i < yn; i++) cout << i << '-' << ry[i] << endl;
// cout << xn << ' ' << yn << endl;
memset(blx, , sizeof(blx));
for (int i = ; i < n; i++) fix(i);
// for (int i = 0; i < pn[0]; i++) cout << poly[0][i].first << ' ' << poly[0][i].second << endl;
for (int i = ; i < n; i++) fill(i);
// for (int j = 0; j < yn; j++) {
// for (int i = 0; i < xn; i++) printf("%d", blx[i][j]);
// puts("");
// }
} int main() {
// freopen("in", "r", stdin);
int T, n, x, y;
cin >> T;
while (T-- && cin >> L >> W) {
xn = yn = ;
L <<= , W <<= ;
rx[xn++] = L, ry[yn++] = W;
rx[xn++] = , ry[yn++] = ;
cin >> n;
for (int i = ; i < n; i++) {
cin >> pn[i];
for (int j = ; j < pn[i]; j++) {
scanf("%d%d", &poly[i][j].first, &poly[i][j].second);
poly[i][j].first <<= , poly[i][j].second <<= ;
rx[xn++] = poly[i][j].first, ry[yn++] = poly[i][j].second;
}
}
PRE(n);
cout << work(n) << endl;
}
return ;
} /*
10
12 8
3
8 5 1 11 1 11 5 7 5 7 4 9 4 9 2 5 2
4 0 3 3 3 3 4 0 4
4 1 4 2 4 2 6 1 6
10 10
3
4 1 1 5 1 5 5 1 5
4 5 3 9 3 9 8 5 8
4 0 5 1 5 1 4 0 4
10 10
1
10 1 1 1 4 0 4 0 5 5 5 5 8 9 8 9 3 5 3 5 1
10 10
1
10 1 1 5 1 5 3 9 3 9 8 5 8 5 5 0 5 0 4 1 4
1000000 1000000
1
8 1 1 1 999999 2 999999 2 999998 999998 999998 999998 999999 999999 999999 999999 1
1000000 1000000
1
8 1 1 1 999999 2 999999 2 2 999998 2 999998 999999 999999 999999 999999 1
1000000 1000000
3
6 1 1 1 999999 2 999999 2 2 999999 2 999999 1
4 3 2 3 1000000 4 1000000 4 2
4 5 2 5 999999 6 999999 6 2
1000000 1000000
4
6 1 1 1 999999 2 999999 2 2 999999 2 999999 1
4 3 2 3 1000000 4 1000000 4 2
4 5 2 5 999999 6 999999 6 2
4 6 999999 7 999999 7 1000000 6 1000000
1000000 1000000
5
6 1 1 1 999999 2 999999 2 2 999999 2 999999 1
4 3 2 3 1000000 4 1000000 4 2
4 5 2 5 999999 6 999999 6 2
4 6 999999 7 999999 7 1000000 6 1000000
4 999999 1 999999 2 1000000 2 1000000 1
1000000 1000000
3
6 1 1 1 999999 2 999999 2 2 999998 2 999998 1
4 999999 3 999999 4 1000000 4 1000000 3
4 999999 3 999999 2 999998 2 999998 3
*/
做题最蛋疼的事情不能理解透题目的意思。做这题的时候，自己不停的出数据坑自己，可是出到那么恶心了都找不到bug。以后还要更加注意细节！
——written by Lyon