18.12.25 POJ 1039 Pipe

描述

The GX Light Pipeline Company started to prepare bent pipes for the new transgalactic light pipeline. During the design phase of the new pipe shape the company ran into the problem of determining how far the light can reach inside each component of the pipe. Note that the material which the pipe is made from is not transparent and not light reflecting.

Each pipe component consists of many straight pipes connected tightly together. For the programming purposes, the company developed the description of each component as a sequence of points [x1; y1], [x2; y2], . . ., [xn; yn], where x1 < x2 < . . . xn . These are the upper points of the pipe contour. The bottom points of the pipe contour consist of points with y-coordinate decreased by 1. To each upper point [xi; yi] there is a corresponding bottom point [xi; (yi)-1] (see picture above). The company wants to find, for each pipe component, the point with maximal x-coordinate that the light will reach. The light is emitted by a segment source with endpoints [x1; (y1)-1] and [x1; y1] (endpoints are emitting light too). Assume that the light is not bent at the pipe bent points and the bent points do not stop the light beam.

输入

The input file contains several blocks each describing one pipe component. Each block starts with the number of bent points 2 <= n <= 20 on separate line. Each of the next n lines contains a pair of real values xi, yi separated by space. The last block is denoted with n = 0.

输出

The output file contains lines corresponding to blocks in input file. To each block in the input file there is one line in the output file. Each such line contains either a real value, written with precision of two decimal places, or the message Through all the pipe.. The real value is the desired maximal x-coordinate of the point where the light can reach from the source for corresponding pipe component. If this value equals to xn, then the message Through all the pipe. will appear in the output file.

样例输入

样例输出

4.67
Through all the pipe.

来源

Central Europe 1995

题解

  1 #include <iostream>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <stack>
  5 #include <string>
  6 #include <math.h>
  7 #include <queue>
  8 #include <stdio.h>
  9 #include <string.h>
 10 #include <set>
 11 #include <vector>
 12 #define maxn 25
 13 #define inf 999999
 14 #define EPS 1e-10
 15 using namespace std;
 16 
 17 int n;
 18 double fin=0;
 19 struct node {
 20     double x, y;
 21     node(){}
 22     node(double a, double b) :x(a), y(b) {}
 23     double length() {
 24         return sqrt(x*x + y * y);
 25     }
 26 }upper[maxn],down[maxn];
 27 typedef node Vector;
 28 node operator + (node a, node b) {
 29     return node(a.x + b.x, a.y + b.y);
 30 }
 31 double operator *(node a, node b) {
 32     return a.x*b.x + a.y*b.y;
 33 }
 34 node operator -(node a, node b) {
 35     return node(a.x - b.x, a.y - b.y);
 36 }
 37 node operator *(double a, node b) {
 38     return node(a*b.x, a*b.y);
 39 }
 40 Vector operator / (Vector a, double b) { 
 41     return Vector(a.x / b, a.y / b); 
 42 }
 43 
 44 double det(node a, node b) {
 45     return a.x*b.y - a.y*b.x;
 46 }
 47 struct line {
 48     node p;
 49     Vector norm;
 50     double dire;
 51     line() {}
 52     line(node a, Vector v) :p(a), norm(v) { dire = atan2(v.y, v.x); }
 53     node getpoint(double x) {
 54         return p + (x - p.x)*(norm/norm.x);
 55     }
 56 };
 57 
 58 Vector cross(line a, line b) {
 59     node p1 = a.p, p2 = a.p + a.norm, p3 = b.p, p4 = b.p + b.norm;
 60     double a1 = det(p3 - p1, p4 - p1), a2 = det(p4 - p2, p3 - p2);
 61     node x = a1*p2;
 62     return (a1*p2 + a2 * p1) / (a1 + a2);
 63 }
 64 
 65 int k;
 66 
 67 bool canthrough(int u, int v) {
 68     node p1 = upper[u], p2 = down[v];
 69     line light = line(p1, p2 - p1);
 70     for (int i = 1; i <= n; i++) {
 71         node q = light.getpoint(upper[i].x);
 72         if (q.y -upper[i].y>EPS|| down[i].y-q.y>EPS) {
 73             k = i;
 74             return false;
 75         }
 76     }
 77     return true;
 78 }
 79 
 80 bool leq(double a, double b) {
 81     if (fabs(a - b) < EPS)return true;
 82     if (a - b > EPS)return true;
 83     return false;
 84 }
 85 
 86 double get(int u, int v) {
 87     double ans = inf;
 88     node p1 = upper[u], p2 = down[v];
 89     line light = line(p1, p2 - p1);
 90     line bar1 = line(upper[k - 1], upper[k] - upper[k - 1]);
 91     line bar2 = line(down[k - 1], down[k] - down[k - 1]);
 92     node q1 = cross(bar1, light), q2 = cross(bar2, light);
 93     if (leq(upper[k].x,q1.x)&&leq(q1.x,upper[k - 1].x)
 94         &&(q2.x- down[k].x > EPS||down[k - 1].x-q2.x > EPS))
 95         ans = q1.x;
 96     else if (leq(down[k].x,q2.x )&&leq(q2.x,down[k - 1].x)
 97         &&(q1.x- upper[k].x > EPS ||upper[k - 1].x-q1.x >EPS))
 98         ans = q2.x;
 99     else if (fabs(q1.x-upper[k - 1].x)<=EPS)
100         ans = q2.x;
101     else if (fabs(q2.x-down[k - 1].x)<=EPS)
102         ans = q1.x;
103     return ans;
104 }
105 
106 void init() {
107     fin = -inf; k = 0;
108     for (int i = 1; i <= n; i++) {
109         scanf("%lf%lf", &upper[i].x, &upper[i].y);
110         down[i] = upper[i];
111         down[i].y--;
112     }
113     for(int i=1;i<=n;i++)
114         for (int j = 1; j <= n; j++) {
115             if (i == j)continue;
116             int oldk = k;
117             if (canthrough(i,j))
118             {
119                 printf("Through all the pipe.
");
120                 return;
121             }
122             if (k < oldk) {
123                 k = oldk;
124                 continue;
125             }
126             double val = get(i, j);
127             if (val-fin>EPS)fin = val;
128         }
129     printf("%.2f
", fin);
130 }
131 
132 int main() {
133     while(scanf("%d",&n)&&n)
134         init();
135     return 0;
136 }

View Code

实在没心情慢慢做了，把上一道改了改

不过还是WA了很多……可能是上一道题让我心思非常浮躁

WA点：

1)浮点数大于等于的判定

2)各种笔误和一开始没想清楚就想当然写上去的地方

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。