理解错题意一个晚上。_(:з」∠)_
题意很容易看懂，就是要求你求出从外面射进一根管子的射线，最远可以射到哪里。
正解的做法是，选择上点和下点各一个，然后对于每个折点位置竖直位置判断经过的点是否在管中。如果是，就继续找，如果不在管中，这时射线必然已经穿过管出去了，这时就要找射线和管上下壁的交点。
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath> using namespace std; const double EPS = 1e-;
const int N = ;
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
bool operator < (Point a) const { return sgn(x - a.x) < || sgn(x - a.x) == && y < a.y;}
bool operator == (Point a) const { return sgn(x - a.x) == && sgn(y - a.y) == ;}
Point operator + (Point a) { return Point(x + a.x, y + a.y);}
Point operator - (Point a) { return Point(x - a.x, y - a.y);}
Point operator * (double p) { return Point(x * p, y * p);}
Point operator / (double p) { return Point(x / p, y / p);}
} ;
typedef Point Vec;
inline double dot(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double cross(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double veclen(Vec x) { return sqrt(dot(x, x));}
inline Point vecunit(Vec x) { return x / veclen(x);}
inline Point normal(Vec x) { return Point(-x.y, x.x) / veclen(x);} struct Line {
Point s, t;
Line() {}
Line(Point s, Point t) : s(s), t(t) {}
Vec vec() { return t - s;}
Point point(double p) { return s + vec() * p;}
} ; Point up[N], dw[N];
Line ul[N], dl[N]; inline Point llint(Point P, Vec u, Point Q, Vec v) { return P + u * (cross(v, P - Q) / cross(u, v));}
bool tstcross(Point a, Point b, Point c, Point d) { return sgn(cross(a - c, b - c)) * sgn(cross(a - d, b - d)) > ;} double cal(Point s, Point t, int n) {
Line tl = Line(s, t);
if (tstcross(tl.s, tl.t, up[], dw[])) return -1e100;
for (int i = ; i < n - ; i++) {
if (tstcross(tl.s, tl.t, up[i + ], dw[i + ])) {
double ret = -1e100;
if (!tstcross(tl.s, tl.t, ul[i].s, ul[i].t)) {
Point tp = llint(tl.s, tl.vec(), ul[i].s, ul[i].vec());
ret = max(ret, tp.x);
}
if (!tstcross(tl.s, tl.t, dl[i].s, dl[i].t)) {
Point tp = llint(tl.s, tl.vec(), dl[i].s, dl[i].vec());
ret = max(ret, tp.x);
}
return ret;
}
}
return 1e100;
} void work(int n) {
for (int i = ; i < n - ; i++) {
ul[i] = Line(up[i], up[i + ]);
dl[i] = Line(dw[i], dw[i + ]);
}
double ans = -1e100;
for (int i = ; i < n; i++) {
for (int j = i + ; j < n; j++) {
if (ans >= 1e99) break;
ans = max(ans, cal(up[i], dw[j], n));
ans = max(ans, cal(dw[i], up[j], n));
}
}
if (ans >= 1e99) puts("Through all the pipe.");
else printf("%.2f\n", ans);
} int main() {
// freopen("in", "r", stdin);
int n;
while (~scanf("%d", &n) && n) {
for (int i = ; i < n; i++) {
scanf("%lf%lf", &up[i].x, &up[i].y);
dw[i] = Point(up[i].x, up[i].y - 1.0);
}
work(n);
}
return ;
}
——written by Lyon