Pipe POJ - 1039(相交）

 1 // 
 2 // Created by HJYL on 2020/1/14.
 3 //
 4 #include <stdio.h>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <vector>
 9 #include <string>
10 #include <cstring>
11 #include <iomanip>
12 using namespace std;
13 const int maxn=100+10;
14 const double eps=1e-8;
15 struct Point{
16     double x,y;
17 };
18 
19 double Cross(Point p1,Point p2,Point p0)
20 {
21     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
22 }
23 
24 bool zx(Point a,Point b,Point c,Point d)
25 {
26     double tmp=Cross(c,a,b)*Cross(d,a,b);
27     if(fabs(tmp)<eps||tmp<0)
28         return true;
29     else
30         return false;
31 }
32 
33 double getpoint(Point a,Point b,Point c,Point d)
34 {
35     double aa=b.y-a.y;
36     double bb=a.x-b.x;
37     double cc=(b.x-a.x)*a.y-(b.y-a.y)*a.x;
38     double aaa=d.y-c.y;
39     double bbb=c.x-d.x;
40     double ccc=(d.x-c.x)*c.y-(d.y-c.y)*c.x;
41     double x=(ccc*bb-cc*bbb)/(aa*bbb-aaa*bb);
42     double y=(cc*aaa-ccc*aa)/(aa*bbb-aaa*bb);
43     return x;
44 }
45 
46 int main()
47 {
48     int n;
49     bool flag;
50     Point above[maxn],below[maxn];
51 
52     while(~scanf("%d",&n)&&n)
53     {
54         for(int i=0;i<n;i++)
55         {
56             scanf("%lf%lf",&above[i].x,&above[i].y);
57             below[i].x=above[i].x;
58             below[i].y=above[i].y-1;
59         }
60         double head=above[0].x;
61         flag=false;
62         int k;
63         for(int i=0;i<n&&!flag;i++)
64         {
65             for(int j=0;j<n&&!flag;j++)
66             {
67                 if(i==j)
68                     break;
69                 for(k=0;k<n;k++)
70                 {
71                     if(!zx(above[i],below[j],above[k],below[k]))//ij连成的线是否与k管道相交
72                         break;
73                 }
74                 if(k==n)
75                     flag=true;
76                 else if(k>max(i,j))
77                 {
78                     head=max(head,getpoint(above[i],below[j],above[k-1],above[k]));
79                     head=max(head,getpoint(above[i],below[j],below[k-1],below[k]));
80                 }
81             }
82         }
83         if(flag)
84             printf("Through all the pipe.\n");
85         else
86             printf("%.2lf\n",head);
87     }
88     return 0;
89 }