poj 1689 && zoj 1422 3002 Rubbery (Geometry + BFS)

　　这题是从校内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

巴特西

poj 1689 && zoj 1422 3002 Rubbery (Geometry + BFS)

最新文章

热门文章