poj 1039 Pipe (Geometry)

　　理解错题意一个晚上。_(:з」∠)_

　　题意很容易看懂，就是要求你求出从外面射进一根管子的射线，最远可以射到哪里。

　　正解的做法是，选择上点和下点各一个，然后对于每个折点位置竖直位置判断经过的点是否在管中。如果是，就继续找，如果不在管中，这时射线必然已经穿过管出去了，这时就要找射线和管上下壁的交点。

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 const double EPS = 1e-6;
11 const int N = 33;
12 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
13 struct Point {
14     double x, y;
15     Point() {}
16     Point(double x, double y) : x(x), y(y) {}
17     bool operator < (Point a) const { return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && y < a.y;}
18     bool operator == (Point a) const { return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;}
19     Point operator + (Point a) { return Point(x + a.x, y + a.y);}
20     Point operator - (Point a) { return Point(x - a.x, y - a.y);}
21     Point operator * (double p) { return Point(x * p, y * p);}
22     Point operator / (double p) { return Point(x / p, y / p);}
23 } ;
24 typedef Point Vec;
25 inline double dot(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
26 inline double cross(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
27 inline double veclen(Vec x) { return sqrt(dot(x, x));}
28 inline Point vecunit(Vec x) { return x / veclen(x);}
29 inline Point normal(Vec x) { return Point(-x.y, x.x) / veclen(x);}
30 
31 struct Line {
32     Point s, t;
33     Line() {}
34     Line(Point s, Point t) : s(s), t(t) {}
35     Vec vec() { return t - s;}
36     Point point(double p) { return s + vec() * p;}
37 } ;
38 
39 
40 Point up[N], dw[N];
41 Line ul[N], dl[N];
42 
43 inline Point llint(Point P, Vec u, Point Q, Vec v) { return P + u * (cross(v, P - Q) / cross(u, v));}
44 bool tstcross(Point a, Point b, Point c, Point d) { return sgn(cross(a - c, b - c)) * sgn(cross(a - d, b - d)) > 0;}
45 
46 double cal(Point s, Point t, int n) {
47     Line tl = Line(s, t);
48     if (tstcross(tl.s, tl.t, up[0], dw[0])) return -1e100;
49     for (int i = 0; i < n - 1; i++) {
50         if (tstcross(tl.s, tl.t, up[i + 1], dw[i + 1])) {
51             double ret = -1e100;
52             if (!tstcross(tl.s, tl.t, ul[i].s, ul[i].t)) {
53                 Point tp = llint(tl.s, tl.vec(), ul[i].s, ul[i].vec());
54                 ret = max(ret, tp.x);
55             }
56             if (!tstcross(tl.s, tl.t, dl[i].s, dl[i].t)) {
57                 Point tp = llint(tl.s, tl.vec(), dl[i].s, dl[i].vec());
58                 ret = max(ret, tp.x);
59             }
60             return ret;
61         }
62     }
63     return 1e100;
64 }
65 
66 void work(int n) {
67     for (int i = 0; i < n - 1; i++) {
68         ul[i] = Line(up[i], up[i + 1]);
69         dl[i] = Line(dw[i], dw[i + 1]);
70     }
71     double ans = -1e100;
72     for (int i = 0; i < n; i++) {
73         for (int j = i + 1; j < n; j++) {
74             if (ans >= 1e99) break;
75             ans = max(ans, cal(up[i], dw[j], n));
76             ans = max(ans, cal(dw[i], up[j], n));
77         }
78     }
79     if (ans >= 1e99) puts("Through all the pipe.");
80     else printf("%.2f
", ans);
81 }
82 
83 int main() {
84 //    freopen("in", "r", stdin);
85     int n;
86     while (~scanf("%d", &n) && n) {
87         for (int i = 0; i < n; i++) {
88             scanf("%lf%lf", &up[i].x, &up[i].y);
89             dw[i] = Point(up[i].x, up[i].y - 1.0);
90         }
91         work(n);
92     }
93     return 0;
94 }

View Code

——written by Lyon