POJ 3525 - Most Distant Point from the Sea

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

概要

凸な n 角形が与えられるので，その内部の点で，各辺との距離の最小値が最大となるような点を答える．

制約

解法

答えを D とすると，d >= D な任意の d に対して，各辺から内部の方向に距離 d の直線で多角形を切断すると，何も残らなくなる．

よって，この d に関して二分探索すればよい．

山登り法でも解けると思ったけど，うまくいかなかった．

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