POJ 1039 - Pipe

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

概要

座標の列 (x[1], y[1]), ..., (x[n], y[n]) が与えられ，(x[1], y[1]), ..., (x[n], y[n]) と (x[1], y[1]-1), ..., (x[n], y[n]-1) からなるパイプを示している (図を見ると意味がわかりやすい)．

(x[1], y[1]) のほうからパイプ内に光を当てたとき，到達しうる最大の x 座標を答える． ただし，パイプを抜ける場合は「Through all the pipe.」と出力する．

パイプは全く光を通さないし，全く反射もしないとする．

制約

解法

直線が最も右側まで伸びるのは

のいずれか．

last_index() でそのような直線がどこまで進めるかを計算し，もし n 番目まで進めるならすぐに「Through all the pipe.」を出力し，そうでなかったら last_index() の次の区間での交点を計算して最大値をとる，というように実装した．

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <vector>
 4 #include <complex>
 5 #include <limits>
 6 using namespace std;
 7 typedef complex<double> P;
 8 static const double EPS = 1e-6;
 9 
10 inline bool feq(double x, double y) { return abs(x - y) < EPS; }
11 inline bool fleq(double x, double y) { return x <= y + EPS; }
12 inline double cross(const P& a, const P& b) { return a.real()*b.imag() - b.real()*a.imag(); }
13 
14 struct line
15 {
16   P a, b;
17   line(const P& x, const P& y) : a(x), b(y) {}
18 };
19 
20 struct segment
21 {
22   P a, b;
23   segment(const P& x, const P& y) : a(x), b(y) {}
24   inline bool intersects(const line& ln) const
25   {
26     return cross(ln.b-ln.a, a-ln.a) * cross(ln.b-ln.a, b-ln.a) < EPS;
27   }
28 
29   inline P intersection(const line& ln) const
30   {
31     const P x = b - a;
32     const P y = ln.b - ln.a;
33     return a + x*(cross(y, ln.a-a)/cross(y, x));
34   }
35 };
36 
37 int last_index(const vector<pair<P,P> >& v, const P& left, const P& right)
38 {
39   const int N = v.size();
40   const P e = (right - left) / abs(right - left);
41   for (int i = 0; i < N; i++) {
42     const double scale = (v[i].first.real() - left.real()) / e.real();
43     P p = left + scale*e;
44     if (!fleq(v[i].second.imag(), p.imag()) || !fleq(p.imag(), v[i].first.imag())) {
45       return i-1;
46     }
47   }
48   return N-1;
49 }
50 
51 double update(double ans, const P& left, const P& right, const pair<P,P>& beg, const pair<P,P>& end)
52 {
53   const line ln(left, right);
54   const segment s1(beg.first, end.first);
55   const segment s2(beg.second, end.second);
56   if (s1.intersects(ln)) {
57     ans = max(ans, s1.intersection(ln).real());
58   }
59   if (s2.intersects(ln)) {
60     ans = max(ans, s2.intersection(ln).real());
61   }
62   return ans;
63 }
64 
65 int main()
66 {
67   int N;
68   while (scanf("%d", &N) != EOF && N != 0) {
69     vector<pair<P,P> > v(N);
70     for (int i = 0; i < N; i++) {
71       double x, y;
72       scanf("%lf %lf", &x, &y);
73       v[i] = make_pair(P(x, y), P(x, y-1));
74     }
75 
76     double ans = -numeric_limits<double>::max();
77     for (int i = 0; i < N; i++) {
78       for (int j = i+1; j < N; j++) {
79         const int k = last_index(v, v[i].first, v[j].second);
80         const int l = last_index(v, v[i].second, v[j].first);
81         if (max(k, l) == N-1) {
82           puts("Through all the pipe.");
83           goto NEXT;
84         } else {
85           if (j <= k) {
86             ans = update(ans, v[i].first, v[j].second, v[k], v[k+1]);
87           }
88           if (j <= l) {
89             ans = update(ans, v[i].second, v[j].first, v[l], v[l+1]);
90           }
91         }
92       }
93     }
94     printf("%.2f\n", ans);
95 NEXT:
96     ;
97   }
98   return 0;
99 }
poj/1039.cc