POJ 3130 - How I Mathematician Wonder What You Are!

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

概要

平面図形 F について，任意の点 P ∈ F に対して，線分 CP が F に含まれるような点 C ∈ F が存在するとき，F は start-shaped である．

与えられた n 角形が start-shaped であるかどうか答える．

制約

• 4 <= n <= 50
• 0 <= 座標 <= 10000
• 多角形の座標は反時計回りに与えられる
• 多角形は simple である．つまり，辺は交差していない
• 各辺を無限に伸ばしたとしても，3つ以上の辺が1点で交わることはない(?)

解法

POJ 3335 - Rotating Scoreboard と同じ．

 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     return abs(cross(ln.b - ln.a, b - a)) < EPS;
41   }
42 };
43 
44 struct polygon
45 {
46   vector<P> ps;
47   polygon() {}
48   polygon(const vector<P>& v) : ps(v) {}
49 
50   inline int size() const { return ps.size(); }
51   inline void push_back(const P& p) { ps.push_back(p); }
52   inline P& operator[](int i) { return ps[i]; }
53   inline const P& operator[](int i) const { return ps[i]; }
54 
55   polygon cut(const line& ln) const
56   {
57     // cut out the left-side of the line
58     const int N = ps.size();
59     polygon ret;
60     for (int i = 0; i < N; i++) {
61       const segment seg(ps[i], ps[(i+1)%N]);
62       if (cross(ln.b - ln.a, ps[i] - ln.a) < EPS) {
63         // ps[i] is right-side of the line
64         ret.push_back(ps[i]);
65         if (!seg.parallel(ln) && seg.intersects(ln)) {
66           const P p = seg.intersection(ln);
67           if (abs(p - ps[i]) > EPS) {
68             ret.push_back(p);
69           }
70         }
71       } else if (!seg.parallel(ln) && seg.intersects(ln)) {
72         ret.push_back(seg.intersection(ln));
73       }
74     }
75     return ret;
76   }
77 };
78 
79 int main()
80 {
81   int N;
82   while (scanf("%d", &N) != EOF && N != 0) {
83     polygon poly;
84     for (int i = 0; i < N; i++) {
85       int x, y;
86       scanf("%d %d", &x, &y);
87       poly.push_back(P(x, y));
88     }
89 
90     polygon ans = poly;
91     for (int i = 0; i < N; i++) {
92       ans = ans.cut(line(poly[(i+1)%N], poly[i]));
93     }
94     printf("%d\n", !ans.ps.empty());
95   }
96   return 0;
97 }