LA 3263 That Nice Euler Circuit (2D Geometry)

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1264

　　看刘汝佳的训练指南过的第一道计算几何题。开始的时候看到这题就觉得这是水题，于是瞬间就把代码打出来了。不过在debug的时候，搞着搞着发现如果像我一开始的时候那样做，好多特殊情况不能正常处理，加了好多特判都还是能找出bug。最后在搞出下面那么多数据，觉得这样特判简直就是一个无底洞，根本就不能正确的得到答案。。。- - 最后在wa到忍不住的情况下，只好求助于佳哥的题解了。。

　　看了一下他的代码，瞬间觉得豁然开朗，原来之前那么的多的特判都可以通过这样的方法来消除。

　　简单说一下他的做法。首先，我们可以知道顶点数V+边数E-面数F=2这个基本定理。然后，这个图形的顶点数是可以在两两判相交的时候得到的，我用一个set来保存这些个数。边数是解这题的一个关键，边数至少有n-1条，这是显而易见的，然而某些边是被分割成多少段呢？这时候就需要将我们找到的点放进线段，看看有没有将一条线段分割，有的话就将总的边数加一。因为将点放进set里了，所以所有点都是唯一的。也就是不会有同一个位置的点对同一条线段分割多于一次。最后套进欧拉定理，就可以正确的把这题解决了。

代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <set>
  5 #include <vector>
  6 #include <iostream>
  7 #include <algorithm>
  8 
  9 using namespace std;
 10 
 11 #define REP(i, n) for (int i = 0; i < (n); i++)
 12 
 13 struct Point {
 14     double x, y;
 15     Point() {}
 16     Point(double x, double y) : x(x), y(y) {}
 17 } ;
 18 template<class T> T sqr(T x) { return x * x;}
 19 
 20 // basic calculations
 21 typedef Point Vec;
 22 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
 23 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
 24 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
 25 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
 26 
 27 const double eps = 1e-8;
 28 int sgn(double x) { return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1);}
 29 bool operator < (Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y);}
 30 bool operator == (Point a, Point b) { return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;}
 31 
 32 double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
 33 double vecLen(Vec x) { return sqrt(sqr(x.x) + sqr(x.y));}
 34 double angle(Vec a, Vec b) { return acos(dotDet(a, b) / vecLen(a) / vecLen(b));}
 35 double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
 36 double triArea(Point a, Point b, Point c) { return fabs(crossDet(b - a, c - a));}
 37 Vec rotate(Vec x, double rad) { return Vec(x.x * cos(rad) - x.y * sin(rad), x.x * sin(rad) + x.y * cos(rad));}
 38 Vec normal(Vec x) {
 39     double len = vecLen(x);
 40     return Vec(- x.y / len, x.x / len);
 41 }
 42 
 43 struct Line {
 44     Point s, t;
 45     Line() {}
 46     Line(Point s, Point t) : s(s), t(t) {}
 47 } ;
 48 typedef Line Seg;
 49 
 50 bool onSeg(Point x, Point a, Point b) { return sgn(crossDet(a - x, b - x)) == 0 && sgn(dotDet(a - x, b - x)) < 0;}
 51 bool onSeg(Point x, Seg s) { return onSeg(x, s.s, s.t);}
 52 // 0 : not intersect
 53 // 1 : proper intersect
 54 // 2 : improper intersect
 55 int segIntersect(Point a, Point c, Point b, Point d) {
 56     Vec v1 = b - a, v2 = c - b, v3 = d - c, v4 = a - d;
 57     int a_bc = sgn(crossDet(v1, v2));
 58     int b_cd = sgn(crossDet(v2, v3));
 59     int c_da = sgn(crossDet(v3, v4));
 60     int d_ab = sgn(crossDet(v4, v1));
 61     if (a_bc * c_da > 0 && b_cd * d_ab > 0) return 1;
 62     if (onSeg(b, a, c) && c_da) return 2;
 63     if (onSeg(c, b, d) && d_ab) return 2;
 64     if (onSeg(d, c, a) && a_bc) return 2;
 65     if (onSeg(a, d, b) && b_cd) return 2;
 66     return 0;
 67 }
 68 int segIntersect(Seg a, Seg b) { return segIntersect(a.s, a.t, b.s, b.t);}
 69 
 70 // point of the intersection of 2 lines
 71 Point lineIntersect(Point P, Vec v, Point Q, Vec w) {
 72     Vec u = P - Q;
 73     double t = crossDet(w, u) / crossDet(v, w);
 74     return P + v * t;
 75 }
 76 Point lineIntersect(Line a, Line b) { return lineIntersect(a.s, a.t - a.s, b.s, b.t - b.s);}
 77 
 78 // directed distance
 79 double pt2Line(Point x, Point a, Point b) {
 80     Vec v1 = b - a, v2 = x - a;
 81     return crossDet(v1, v2) / vecLen(v1);
 82 }
 83 double pt2Line(Point x, Line L) { return pt2Line(x, L.s, L.t);}
 84 
 85 double pt2Seg(Point x, Point a, Point b) {
 86     if (a == b) return vecLen(x - a);
 87     Vec v1 = b - a, v2 = x - a, v3 = x - b;
 88     if (sgn(dotDet(v1, v2)) < 0) return vecLen(v2);
 89     if (sgn(dotDet(v1, v3)) > 0) return vecLen(v3);
 90     return fabs(crossDet(v1, v2)) / vecLen(v1);
 91 }
 92 double pt2Seg(Point x, Seg s) { return pt2Seg(x, s.s, s.t);}
 93 
 94 struct Poly {
 95     vector<Point> pt;
 96     Poly() {}
 97     Poly(vector<Point> pt) : pt(pt) {}
 98     double area() {
 99         double ret = 0.0;
100         int sz = pt.size();
101         for (int i = 1; i < sz; i++) {
102             ret += crossDet(pt[i], pt[i - 1]);
103         }
104         return fabs(ret / 2.0);
105     }
106 } ;
107 
108 /****************** template above *******************/
109 
110 Poly poly;
111 
112 int main() {
113 //    freopen("in", "r", stdin);
114     int cas = 1, n;
115     while (cin >> n && n) {
116         set<Point> pt;
117         pt.clear();
118         poly.pt.clear();
119         int ln = n - 1;
120         double x, y;
121         for (int i = 0; i < n; i++) {
122             cin >> x >> y;
123             poly.pt.push_back(Point(x, y));
124             pt.insert(Point(x, y));
125             for (int j = 1; j < i; j++) {
126                 int st = segIntersect(Line(poly.pt[i - 1], poly.pt[i]), Line(poly.pt[j - 1], poly.pt[j]));
127                 if (st == 1) {
128                     pt.insert(lineIntersect(Line(poly.pt[i - 1], poly.pt[i]), Line(poly.pt[j - 1], poly.pt[j])));
129                 }
130             }
131         }
132         for (set<Point>::iterator si = pt.begin(); si != pt.end(); si++) {
133             for (int i = 1; i < n; i++) {
134                 if (onSeg(*si, poly.pt[i - 1], poly.pt[i])) ln++;
135             }
136         }
137         cout << "Case " << cas++ << ": There are " << ln - pt.size() + 2 << " pieces." << endl;
138     }
139     return 0;
140 }

数据如下：

View Code

  1 5
  2 0 0
  3 0 1
  4 1 1
  5 1 0
  6 0 0
  7 
  8 7
  9 1 1
 10 1 5
 11 2 1
 12 2 5
 13 5 1
 14 3 5
 15 1 1
 16 
 17 11
 18 0 0
 19 4 0
 20 8 0
 21 8 1
 22 7 0
 23 6 1
 24 4 0
 25 3 1
 26 2 0
 27 0 1
 28 0 0
 29 
 30 7
 31 0 0
 32 1 0
 33 2 0
 34 2 1
 35 1 0
 36 0 1
 37 0 0
 38 
 39 12
 40 0 0
 41 1 -1
 42 2 0
 43 1 1
 44 0 0
 45 2 0
 46 2 1
 47 0 1
 48 0 0
 49 -1 -1
 50 0 -1
 51 0 0
 52 
 53 11
 54 0 0
 55 4 0
 56 8 0
 57 8 1
 58 7 0
 59 6 1
 60 4 0
 61 3 1
 62 2 0
 63 0 1
 64 0 0
 65 
 66 5
 67 0 0
 68 10 0
 69 5 5
 70 5 -5
 71 0 0
 72 
 73 7
 74 0 0
 75 0 -1
 76 1 0
 77 -1 0
 78 1 -2
 79 1 1
 80 0 0
 81 
 82 11
 83 0 0
 84 1 0
 85 1 1
 86 -1 -1
 87 0 -1
 88 0 1
 89 -1 1
 90 1 -1
 91 0 -2
 92 -2 0
 93 0 0
 94 
 95 14
 96 0 0
 97 1 0
 98 1 1
 99 -1 -1
100 0 -1
101 0 1
102 -1 1
103 1 -1
104 0 -2
105 -2 0
106 0 0
107 100 101
108 99 101
109 0 0
110 
111 16
112 0 0
113 1 0
114 1 1
115 -1 -1
116 0 -1
117 0 1
118 -1 1
119 1 -1
120 0 -2
121 -2 0
122 0 0
123 100 101
124 99 101
125 -99 -101
126 -100 -101
127 0 0
128 
129 0

——written by Lyon