uva 12296 Pieces and Discs （Geometry）

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3717
　　暴力计算几何。用切割多边形的方法，将初始的矩形划分成若干个多边形，然后对于每一个圆判断有哪些多边形是与其相交的。面积为0的多边形忽略。
　　对于多边形与圆相交，要主意圆在多边形内的情况。
代码如下：
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <vector>
  5 #include <iostream>
  6 #include <algorithm>
  7 
  8 using namespace std;
  9 
 10 const double EPS = 1e-8;
 11 const double PI = acos(-1.0);
 12 template <class T> T sqr(T x) { return x * x;}
 13 struct Point {
 14     double x, y;
 15     Point() {}
 16     Point(double x, double y) : x(x), y(y) {}
 17 } ;
 18 typedef Point Vec;
 19 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
 20 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
 21 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
 22 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
 23 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
 24 bool operator < (Point a, Point b) { return sgn(a.x - b.x) < 0 || sgn(a.x - b.x) == 0 && a.y < b.y;}
 25 bool operator == (Point a, Point b) { return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;}
 26 
 27 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
 28 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
 29 inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
 30 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
 31 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
 32 inline Vec vecUnit(Vec x) { return x / vecLen(x);}
 33 inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);}
 34 inline bool onSeg(Point x, Point a, Point b) { return sgn(crossDet(x, a, b)) == 0 && sgn(dotDet(x, a, b)) < 0;}
 35 
 36 int segIntersect(Point a, Point c, Point b, Point d) {
 37     Vec v1 = b - a, v2 = c - b, v3 = d - c, v4 = a - d;
 38     int a_bc = sgn(crossDet(v1, v2));
 39     int b_cd = sgn(crossDet(v2, v3));
 40     int c_da = sgn(crossDet(v3, v4));
 41     int d_ab = sgn(crossDet(v4, v1));
 42 //    cout << a_bc << ' ' << b_cd << ' ' << c_da << ' ' << d_ab << endl;
 43     if (a_bc * c_da > 0 && b_cd * d_ab > 0) return 1;
 44     if (onSeg(b, a, c) && c_da) return 2;
 45     if (onSeg(c, b, d) && d_ab) return 2;
 46     if (onSeg(d, c, a) && a_bc) return 2;
 47     if (onSeg(a, d, b) && b_cd) return 2;
 48     return 0;
 49 }
 50 
 51 Point lineIntersect(Point P, Vec v, Point Q, Vec w) {
 52     Vec u = P - Q;
 53     double t = crossDet(w, u) / crossDet(v, w);
 54     return P + v * t;
 55 }
 56 
 57 struct Poly {
 58     vector<Point> pt;
 59     Poly() { pt.clear();}
 60     ~Poly() {}
 61     Poly(vector<Point> &pt) : pt(pt) {}
 62     Point operator [] (int x) const { return pt[x];}
 63     int size() { return pt.size();}
 64     double area() {
 65         double ret = 0.0;
 66         for (int i = 0, sz = pt.size(); i < sz; i++) {
 67             ret += crossDet(pt[i], pt[(i + 1) % sz]);
 68         }
 69         return fabs(ret / 2.0);
 70     }
 71 } ;
 72 
 73 Poly cutPoly(Poly &poly, Point a, Point b) {
 74     Poly ret = Poly();
 75     int n = poly.size();
 76     for (int i = 0; i < n; i++) {
 77         Point c = poly[i], d = poly[(i + 1) % n];
 78         if (sgn(crossDet(a, b, c)) >= 0) ret.pt.push_back(c);
 79         if (sgn(crossDet(b - a, c - d)) != 0) {
 80             Point ip = lineIntersect(a, b - a, c, d - c);
 81             if (onSeg(ip, c, d)) ret.pt.push_back(ip);
 82         }
 83     }
 84     return ret;
 85 }
 86 
 87 bool isIntersect(Point a, Point b, Poly &poly) {
 88     for (int i = 0, sz = poly.size(); i < sz; i++) {
 89         if (segIntersect(a, b, poly[i], poly[(i + 1) % sz])) return true;
 90     }
 91     return false;
 92 }
 93 
 94 struct Circle {
 95     Point c;
 96     double r;
 97     Circle() {}
 98     Circle(Point c, double r) : c(c), r(r) {}
 99 } ;
100 
101 inline bool inCircle(Point a, Circle c) { return vecLen(c.c - a) < c.r;}
102 bool lineCircleIntersect(Point s, Point t, Circle C, vector<Point> &sol) {
103     Vec dir = t - s, nor = normal(dir);
104     Point mid = lineIntersect(C.c, nor, s, dir);
105     double len = sqr(C.r) - dotDet(C.c - mid, C.c - mid);
106     if (sgn(len) < 0) return 0;
107     if (sgn(len) == 0) {
108         sol.push_back(mid);
109         return 1;
110     }
111     Vec dis = vecUnit(dir);
112     len = sqrt(len);
113     sol.push_back(mid + dis * len);
114     sol.push_back(mid - dis * len);
115     return 2;
116 }
117 
118 bool segCircleIntersect(Point s, Point t, Circle C) {
119     vector<Point> tmp;
120     tmp.clear();
121     if (lineCircleIntersect(s, t, C, tmp)) {
122         if (tmp.size() < 2) return false;
123         for (int i = 0, sz = tmp.size(); i < sz; i++) {
124             if (onSeg(tmp[i], s, t)) return true;
125         }
126     }
127     return false;
128 }
129 
130 vector<Poly> cutPolies(Point s, Point t, vector<Poly> polies) {
131     vector<Poly> ret;
132     ret.clear();
133     for (int i = 0, sz = polies.size(); i < sz; i++) {
134         Poly tmp;
135         tmp = cutPoly(polies[i], s, t);
136         if (tmp.size() >= 3 && tmp.area() > EPS) ret.push_back(tmp);
137         tmp = cutPoly(polies[i], t, s);
138         if (tmp.size() >= 3 && tmp.area() > EPS) ret.push_back(tmp);
139     }
140     return ret;
141 }
142 
143 int ptInPoly(Point p, Poly &poly) {
144     int wn = 0, sz = poly.size();
145     for (int i = 0; i < sz; i++) {
146         if (onSeg(p, poly[i], poly[(i + 1) % sz])) return -1;
147         int k = sgn(crossDet(poly[(i + 1) % sz] - poly[i], p - poly[i]));
148         int d1 = sgn(poly[i].y - p.y);
149         int d2 = sgn(poly[(i + 1) % sz].y - p.y);
150         if (k > 0 && d1 <= 0 && d2 > 0) wn++;
151         if (k < 0 && d2 <= 0 && d1 > 0) wn--;
152     }
153     if (wn != 0) return 1;
154     return 0;
155 }
156 
157 bool circlePoly(Circle C, Poly &poly) {
158     int sz = poly.size();
159     if (ptInPoly(C.c, poly)) return true;
160 //    cout << "~~ " << sz << endl;
161     for (int i = 0; i < sz; i++) {
162 //        cout << poly[i].x << ' ' << poly[i].y << endl;
163         if (inCircle(poly[i], C)) return true;
164 //        cout << i << endl;
165     }
166     for (int i = 0; i < sz; i++) {
167         if (segCircleIntersect(poly[i], poly[(i + 1) % sz], C)) return true;
168 //        cout << i << endl;
169     }
170     return false;
171 }
172 
173 vector<double> circlePolies(Circle C, vector<Poly> &polies) {
174     vector<double> ret;
175     ret.clear();
176     for (int i = 0, sz = polies.size(); i < sz; i++) {
177         if (circlePoly(C, polies[i])) ret.push_back(polies[i].area());
178     }
179     return ret;
180 }
181 
182 const double dir[4][2] = { {0.0, 0.0}, {1.0, 0.0}, {1.0, 1.0}, {0.0, 1.0}};
183 
184 int main() {
185 //    freopen("in", "r", stdin);
186 //    freopen("out", "w", stdout);
187     double L, W;
188     int n, m;
189     while (cin >> n >> m >> L >> W && (n + m + L + W > EPS)) {
190         vector<Poly> cur;
191         cur.push_back(Poly());
192         for (int i = 0; i < 4; i++) {
193             cur[0].pt.push_back(Point(L * dir[i][0], W * dir[i][1]));
194         }
195         Point p[2];
196         for (int i = 0; i < n; i++) {
197             for (int j = 0; j < 2; j++) {
198                 cin >> p[j].x >> p[j].y;
199             }
200             cur = cutPolies(p[0], p[1], cur);
201         }
202 //        cout << cur.size() << endl;
203         Circle C = Circle();
204         for (int i = 0; i < m; i++) {
205             cin >> C.c.x >> C.c.y >> C.r;
206             vector<double> tmp = circlePolies(C, cur);
207             sort(tmp.begin(), tmp.end());
208             cout << tmp.size();
209             for (int j = 0, sz = tmp.size(); j < sz; j++) {
210                 printf(" %.2f", tmp[j]);
211             }
212             cout << endl;
213         }
214         cout << endl;
215     }
216     return 0;
217 }
View Code
——written by Lyon