题目:
给一个管子,有很多转弯处,问从管口的射线射进去最长能射到多远
题解:
根据黑书,可以证明的是这条光线一定经过了一个上顶点和下顶点
所以我们枚举每对上下顶点就可以了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-5
using namespace std;
bool dcmp(double x,double y)
{
if (fabs(x-y)>eps) return 1;
return 0;
}
struct point
{
double x,y;
point () {};
point (double _x,double _y)
{
x=_x,y=_y;
}
point operator + (const point &a)const
{
return point(x+a.x,y+a.y);
}
point operator - (const point &a) const
{
return point(x-a.x,y-a.y);
}
double operator * (const point &a)const
{
return x*a.y-a.x*y;
}
double dot (const point &a,const point &b)
{
return a.x*b.x+a.y*b.y;
}
bool operator < (const point &a)const
{
return x<a.x;
}
bool operator == (const point &a)const
{
return dcmp(x,a.x) && dcmp(y,a.y);
}
}up[105],down[105];
inline double Max(double a,double b)
{
return a>b?a:b;
}
double Multi(point a,point b,point c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
bool Across(point a,point b,point c,point d)
{
double tmp=Multi(c,b,a)*Multi(d,b,a);
if (tmp<0 || fabs(tmp)<eps) return 1;
return 0;
}
double getIntersect(point a,point b,point c,point d)
{
double A1=b.y-a.y,B1=a.x-b.x,C1=(b.x-a.x)*a.y-(b.y-a.y)*a.x;
double A2=d.y-c.y,B2=c.x-d.x,C2=(d.x-c.x)*c.y-(d.y-c.y)*c.x;
return (C2*B1-C1*B2)/(A1*B2-A2*B1);
}
int n,flag;
double ans;
int main()
{
while (scanf("%d",&n) && n)
{
for (int i=0;i<n;i++)
{
scanf("%lf%lf",&up[i].x,&up[i].y);
down[i].x=up[i].x;
down[i].y=up[i].y-1;
}
ans=up[0].x;
flag=0;
for (int i=0;i<n && !flag;i++)
for (int j=0;j<n && !flag;j++)
if (i!=j)
{
int k;
for (k=0;k<n;k++)
if (!Across(up[i],down[j],up[k],down[k])) break;
if (k==n) flag=1;
else if (k>i && k>j)
{
double tmp;
tmp=getIntersect(up[i],down[j],up[k-1],up[k]);
// printf("%.2f\n",tmp);
if (tmp>ans) ans=tmp;
tmp=getIntersect(up[i],down[j],down[k-1],down[k]);
// printf("%.2f\n",tmp);
if (tmp>ans) ans=tmp;
}
}
if (flag) puts("Through all the pipe.");
else printf("%.2f\n",ans);
}
return 0;
}