POJ 2701 - Lapux the Floating Island

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

概要

\(n\) 個の凸な多角形が与えられる。

さらに \(m\) 個の点からなる折れ線が与えられ、これに沿って円が移動する。 円の半径は折れ線の頂点でしか変化せず、線分の途中では一定の大きさである。 このとき、各線分の区間で、円の半径 \(R\) をどの多角形とも重ならないようにできるだけ大きくとった場合の \(R\) の値を、最も近い整数値に丸めたものを答える。 ただし \(R\) は \(R_0 \le R \le R_1\) を満たさなければならない。 そのような \(R\) が存在しないときは \(0\) を答える。

制約

解法

折れ線の頂点でしか半径は変化しないので、各線分の区間について独立に考えることができる。 各線分の区間について、その線分と各多角形の各辺との距離の最小値と \(R_1\) の min が答えである。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <cmath>
  4 #include <complex>
  5 #include <algorithm>
  6 using namespace std;
  7 typedef complex<double> P;
  8 static const double EPS = 1e-6;
  9 
 10 inline double dot(const P& a, const P& b) { return a.real()*b.real() + a.imag()*b.imag(); }
 11 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
 12 
 13 int ccw(const P& a, P b, P c)/*{{{*/
 14 {
 15   b -= a;
 16   c -= a;
 17   if (cross(b, c) > EPS) {
 18     return +1;
 19   } else if (cross(b, c) < -EPS) {
 20     return -1;
 21   } else if (dot(b, c) < -EPS) {
 22     return +2;
 23   } else if (dot(b, b) + EPS < dot(c, c)) {
 24     return -2;
 25   } else {
 26     return 0;
 27   }
 28 }/*}}}*/
 29 
 30 struct segment/*{{{*/
 31 {
 32   P a, b;
 33   segment() {}
 34   segment(const P& x, const P& y) : a(x), b(y) {}
 35 
 36   // AOJ 2402 Milkey Way
 37   inline bool intersects(const segment& seg) const
 38   {
 39     return ccw(a, b, seg.a) * ccw(a, b, seg.b) <= 0
 40       && ccw(seg.a, seg.b, a) * ccw(seg.a, seg.b, b) <= 0;
 41   }
 42 
 43   // AOJ 2402 Milkey Way
 44   inline double distance(const P& p) const
 45   {
 46     if (dot(b-a, p-a) < EPS) {
 47       return abs(p-a);
 48     } else if (dot(a-b, p-b) < EPS) {
 49       return abs(p-b);
 50     } else {
 51       return abs(cross(b-a, p-a))/abs(b-a);
 52     }
 53   }
 54 
 55   // AOJ 2402 Milkey Way
 56   inline double distance(const segment& seg) const
 57   {
 58     if (intersects(seg)) {
 59       return 0;
 60     } else {
 61       return
 62         min(
 63             min(distance(seg.a), distance(seg.b)),
 64             min(seg.distance(a), seg.distance(b)));
 65     }
 66   }
 67 };/*}}}*/
 68 
 69 struct polygon/*{{{*/
 70 {
 71   vector<P> ps;
 72   polygon() {}
 73   polygon(const vector<P>& v) : ps(v) {}
 74 
 75   inline int size() const { return ps.size(); }
 76   inline void push_back(const P& p) { ps.push_back(p); }
 77   inline P& operator[](int i) { return ps[i]; }
 78   inline const P& operator[](int i) const { return ps[i]; }
 79 
 80   double distance(const segment& seg) const
 81   {
 82     const int N = size();
 83     double ans = 1e10;
 84     for (int i = 0; i < N; i++) {
 85       ans = min(ans, seg.distance(segment(ps[i], ps[(i+1)%N])));
 86     }
 87     return ans;
 88   }
 89 };/*}}}*/
 90 
 91 int main()
 92 {
 93   double R0, R1;
 94   int N;
 95   while (scanf("%lf %lf %d", &R0, &R1, &N) != EOF && N != 0) {
 96     vector<polygon> v;
 97     for (int i = 0; i < N; i++) {
 98       int M;
 99       scanf("%d", &M);
100       polygon p;
101       for (int j = 0; j < M; j++) {
102         double x, y;
103         scanf("%lf %lf", &x, &y);
104         p.push_back(P(x, y));
105       }
106       v.push_back(p);
107     }
108     int M;
109     scanf("%d", &M);
110     vector<P> path;
111     for (int i = 0; i < M; i++) {
112       double x, y;
113       scanf("%lf %lf", &x, &y);
114       path.push_back(P(x, y));
115     }
116 
117     for (int i = 0; i < M-1; i++) {
118       const segment seg(path[i], path[i+1]);
119       double d = R1;
120       for (vector<polygon>::const_iterator it = v.begin(); it != v.end(); ++it) {
121         d = min(d, it->distance(seg));
122       }
123       if (i != 0) {
124         putchar(' ');
125       }
126       if (d < R0) {
127         putchar('0');
128       } else {
129         printf("%ld", lround(d));
130       }
131     }
132     putchar('\n');
133   }
134   return 0;
135 }
poj/2701.cc