uva 11665 Chinese Ink (几何+并查集)

UVA 11665

　　随便给12的找了一道我没做过的几何基础题。这题挺简单的，不过uva上通过率挺低，通过人数也不多。

　　题意是要求给出的若干多边形组成多少个联通块。做的时候要注意这题是不能用double浮点类型的，然后判多边形交只需要两个条件，存在边规范相交，或者存在一个多边形上的顶点在另一个多边形上或者在多边形内。

代码如下：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const double EPS = 1e-;

 const int N = ;

 const int M = ;

 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}

 struct Point {

     int x, y;

     Point() {}

     Point(int x, int y) : x(x), y(y) {}

     Point operator + (Point a) { return Point(x + a.x, y + a.y);}

     Point operator - (Point a) { return Point(x - a.x, y - a.y);}

     Point operator * (int p) { return Point(x * p, y * p);}

     Point operator / (int p) { return Point(x / p, y / p);}

 } ;

 inline int cross(Point a, Point b) { return a.x * b.y - a.y * b.x;}

 inline int dot(Point a, Point b) { return a.x * b.x + a.y * b.y;}

 inline bool onseg(Point x, Point a, Point b) { return sgn(cross(a - x, b - x)) ==  && sgn(dot(a - x, b - x)) <= ;}

 bool ptinpoly(Point x, Point *pt, int n) {

     pt[n] = pt[];

     int wn = ;

     for (int i = ; i < n; i++) {

         if (onseg(x, pt[i], pt[i + ])) return true;

         int dr = sgn(cross(pt[i + ] - pt[i], x - pt[i]));

         int k1 = sgn(pt[i + ].y - x.y);

         int k2 = sgn(pt[i].y - x.y);

         if (dr >  && k1 >  && k2 <= ) wn++;

         if (dr <  && k2 >  && k1 <= ) wn--;

     }

     return wn != ;

 }

 struct MFS {

     int fa[N], cnt;

     void init() { for (int i = ; i < N; i++) fa[i] = i; cnt = ;}

     int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]);}

     void merge(int x, int y) {

         int fx = find(x);

         int fy = find(y);

         if (fx == fy) return ;

         cnt++;

         fa[fx] = fy;

     }

 } mfs;

 Point poly[N][M];

 char buf[];

 int sz[N];

 bool ssint(Point a, Point b, Point c, Point d) {

     int s1 = sgn(cross(a - c, b - c));

     int s2 = sgn(cross(a - d, b - d));

     int t1 = sgn(cross(c - a, d - a));

     int t2 = sgn(cross(c - b, d - b));

     return s1 * s2 <  && t1 * t2 < ;

 }

 bool polyint(int a, int b) {

     poly[a][sz[a]] = poly[a][];

     poly[b][sz[b]] = poly[b][];

     for (int i = ; i < sz[a]; i++) {

         for (int j = ; j < sz[b]; j++) {

             if (ssint(poly[a][i], poly[a][i + ], poly[b][j], poly[b][j + ])) return true;

         }

     }

     return false;

 }

 bool test(int a, int b) {

     for (int i = ; i < sz[a]; i++) if (ptinpoly(poly[a][i], poly[b], sz[b])) return true;

     for (int i = ; i < sz[b]; i++) if (ptinpoly(poly[b][i], poly[a], sz[a])) return true;

     if (polyint(a, b)) return true;

     return false;

 }

 int main() {

     //freopen("in", "r", stdin);

     int n;

     while (cin >> n && n) {

         gets(buf);

         char *p;

         mfs.init();

         for (int i = ; i < n; i++) {

             gets(buf);

             p = strtok(buf, " ");

             for (sz[i] = ; p; sz[i]++) {

                 sscanf(p, "%d", &poly[i][sz[i]].x);

                 p = strtok(NULL, " ");

                 sscanf(p, "%d", &poly[i][sz[i]].y);

                 p = strtok(NULL, " ");

             }

             //cout << sz[i] << endl;

             for (int j = ; j < i; j++) if (test(i, j)) {

                 mfs.merge(i, j);

                 //cout << i << ' ' << j << endl;

             }

         }

         cout << n - mfs.cnt << endl;

     }

     return ;

 }

——written by Lyon