POJ 1279 - Art Gallery

http://poj.org/problem?id=1279

概要

N 頂点の多角形(凸とは限らない)が与えられ，辺上のどの位置からも見える多角形の内側の領域の面積を答える．

制約

解法

各辺に沿って多角形を切断し，残った多角形の面積を出力する．

  1 #include <cstdio>
  2 #include <vector>
  3 #include <complex>
  4 #include <cmath>
  5 using namespace std;
  6 typedef complex<double> P;
  7 static const double EPS = 1e-6;
  8 static const double PI = acos(-1.0);
  9 
 10 inline double cross(const P& a, const P& b)
 11 {
 12   return a.real()*b.imag() - b.real()*a.imag();
 13 }
 14 
 15 struct line
 16 {
 17   P a, b;
 18   line() {}
 19   line(const P& x, const P& y) : a(x), b(y) {}
 20 };
 21 
 22 struct segment
 23 {
 24   P a, b;
 25   segment(const P& x, const P& y) : a(x), b(y) {}
 26   inline bool intersects(const line& ln) const
 27   {
 28     return cross(ln.b - ln.a, a - ln.a) * cross(ln.b - ln.a, b - ln.a) < EPS;
 29   }
 30 
 31   inline P intersection(const line& ln) const
 32   {
 33     const P x = b - a;
 34     const P y = ln.b - ln.a;
 35     return a + x*(cross(y, ln.a - a))/cross(y, x);
 36   }
 37 
 38   inline bool parallel(const line& ln) const
 39   {
 40     const double a = abs(arg(b - a) - arg(ln.b - ln.a));
 41     return a < EPS || abs(PI - a) < EPS;
 42   }
 43 };
 44 
 45 struct polygon
 46 {
 47   vector<P> ps;
 48   polygon() {}
 49   polygon(const vector<P>& v) : ps(v) {}
 50 
 51   inline int size() const { return ps.size(); }
 52   inline void push_back(const P& p) { ps.push_back(p); }
 53   inline P& operator[](int i) { return ps[i]; }
 54   inline const P& operator[](int i) const { return ps[i]; }
 55 
 56   double area() const
 57   {
 58     // positive if polygon is clockwise
 59     double a = 0.0;
 60     const int N = ps.size();
 61     for (int i = 0; i < N; i++) {
 62       a += cross(ps[(i+1)%N], ps[i]);
 63     }
 64     return a/2.0;
 65   }
 66 
 67   polygon cut(const line& ln) const
 68   {
 69     // cut out the left-side of the line
 70     const int N = ps.size();
 71     polygon ret;
 72     for (int i = 0; i < N; i++) {
 73       const segment seg(ps[i], ps[(i+1)%N]);
 74       if (cross(ln.b - ln.a, ps[i] - ln.a) < EPS) {
 75         // ps[i] is right-side of the line
 76         ret.push_back(ps[i]);
 77         if (!seg.parallel(ln) && seg.intersects(ln)) {
 78           const P p = seg.intersection(ln);
 79           if (abs(p - ps[i]) > EPS) {
 80             ret.push_back(p);
 81           }
 82         }
 83       } else if (!seg.parallel(ln) && seg.intersects(ln)) {
 84         ret.push_back(seg.intersection(ln));
 85       }
 86     }
 87     return ret;
 88   }
 89 };
 90 
 91 int main()
 92 {
 93   int T;
 94   scanf("%d", &T);
 95   while (T-- > 0) {
 96     int N;
 97     scanf("%d", &N);
 98     polygon poly;
 99     for (int i = 0; i < N; i++) {
100       int x, y;
101       scanf("%d %d", &x, &y);
102       poly.push_back(P(x, y));
103     }
104 
105     polygon ans = poly;
106     for (int i = 0; i < N; i++) {
107       ans = ans.cut(line(poly[i], poly[(i+1)%N]));
108     }
109     printf("%.2f\n", ans.area());
110   }
111   return 0;
112 }
poj/1279.cc