POJ 1584 - A Round Peg in a Ground Hole

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

概要

\(N\) 角形の穴があり、座標 \((X, Y)\) に半径 \(R\) の杭を打つ。

まず穴に突出した部位が無いこと、すなわち多角形の内部の任意の2点について、その2点を結ぶ線分が多角形の辺と交わらないことを判定する。 もし突出した部位が無い場合、杭を与えられた座標に打ったときに、きちんと穴の中に収まるかどうかを答える。

制約

解法

一つ目の条件は「凸多角形かどうか」と言い換えることができる。

二つ目の条件は中心と各辺との距離がすべて \(R\) 以上であることを調べる。 そもそも座標が多角形の内部に無いケースもあることに注意。

  1 #include <iostream>
  2 #include <vector>
  3 #include <complex>
  4 #include <algorithm>
  5 using namespace std;
  6 typedef complex<double> P;
  7 static const double EPS = 1e-6;
  8 
  9 inline double dot(const P& a, const P& b) { return a.real()*b.real() + a.imag()*b.imag(); }
 10 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 11 
 12 int ccw(const P& a, P b, P c)/*{{{*/
 13 {
 14   b -= a;
 15   c -= a;
 16   if (cross(b, c) > EPS) {
 17     // counter clockwise
 18     return +1;
 19   } else if (cross(b, c) < -EPS) {
 20     // clockwise
 21     return -1;
 22   } else if (dot(b, c) < -EPS) {
 23     // c-a-b on line
 24     return +2;
 25   } else if (dot(b, b) + EPS < dot(c, c)) {
 26     // a-b-c on line
 27     return -2;
 28   } else {
 29     return 0;
 30   }
 31 }/*}}}*/
 32 
 33 struct segment/*{{{*/
 34 {
 35   P a, b;
 36   segment() {}
 37   segment(const P& x, const P& y) : a(x), b(y) {}
 38 
 39   // AOJ 2402 Milkey Way
 40   inline double distance(const P& p) const
 41   {
 42     if (dot(b-a, p-a) < EPS) {
 43       return abs(p-a);
 44     } else if (dot(a-b, p-b) < EPS) {
 45       return abs(p-b);
 46     } else {
 47       return abs(cross(b-a, p-a))/abs(b-a);
 48     }
 49   }
 50 };/*}}}*/
 51 
 52 bool formed(const vector<P>& ps)
 53 {
 54   const int N = ps.size();
 55   for (int i = 0; i < N; i++) {
 56     if (ccw(ps[i], ps[(i+1)%N], ps[(i+2)%N]) == -1) {
 57       return false;
 58     }
 59   }
 60   return true;
 61 }
 62 
 63 bool fit(double R, const P& o, const vector<P>& ps)
 64 {
 65   const int N = ps.size();
 66   for (int i = 0; i < N; i++) {
 67     const segment s(ps[i], ps[(i+1)%N]);
 68     if (ccw(s.a, o, s.b) == 1) {
 69       return false;
 70     }
 71     if (s.distance(o) + EPS < R) {
 72       return false;
 73     }
 74   }
 75   return true;
 76 }
 77 
 78 int main()
 79 {
 80   for (int N; cin >> N && N >= 3;) {
 81     double R;
 82     P o;
 83     cin >> R >> o.real() >> o.imag();
 84     vector<P> ps(N);
 85     for (int i = 0; i < N; i++) {
 86       cin >> ps[i].real() >> ps[i].imag();
 87     }
 88 
 89     // make it counter-clockwise
 90     for (int i = 0; i < N; i++) {
 91       if (ccw(ps[i], ps[(i+1)%N], ps[(i+2)%N]) == -1) {
 92         reverse(ps.begin(), ps.end());
 93       }
 94     }
 95 
 96     if (!formed(ps)) {
 97       cout << "HOLE IS ILL-FORMED" << endl;
 98     } else if (fit(R, o, ps)) {
 99       cout << "PEG WILL FIT" << endl;
100     } else {
101       cout << "PEG WILL NOT FIT" << endl;
102     }
103   }
104   return 0;
105 }
poj/1584.cc