http://poj.org/problem?id=1039
黑书P359例题
题目要我们求出光线在Pipe里能射到的最远处的x坐标。我们只要找出其中一条最优光线。
一条最优光线必须满足的一个必要条件是：它必定过Pipe的一个上顶点和一个下顶点。否则，我们总可以通过平移或是旋转使光线走更远的距离。有了这个条件，就可以通过枚举所有的上下顶点对（i，j），找出最优的。
过上下顶点的光线共有n*n条，要求的就是
Max{X(i,j) | 过上下顶点对(i,j)能达到的最远距离的横坐标} （i=0..n-1,j=0..n-1;）
光线（i，j）要能进入了k-1到k这一节，则它比与（0，0）..（k-1，k-1）都相交。并且当（i，j）与（0，0）..（k-1，k-1）都相交,而与(k,k)不交时，他必与上边或下边(k-1,k)相交。显然当k<=MAX(i,j)时，我们便不用处理(i,j)，因为它或者不是最优光线，或者会在其他的(i’,j’)求出。对k>Max(i,j),求出(i,j)与上/下边（k-1,k）的交点的x坐标，并与当前最大值比较，决定取舍。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define eps 1e-8
using namespace std;
int n;
struct point
{
double x,y;
};
struct it
{
point a,b;
}p[25];
double multi(point p0,point p1,point p2)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
point inter(point u1,point u2,point v1,point v2)
{
point ret=u1;
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
bool judge(point p1,point p2,point p3,point p4)
{
if(multi(p1,p2,p4)*multi(p1,p2,p3)>eps)
return false;
else
return true;
}
double work(int i,int j)
{
int k;
point t1,t2;
double m=p[0].a.x;
for(k=0;k<n;k++)
{
if(!judge(p[i].a,p[j].b,p[k].a,p[k].b))
{
if(k==0)
return p[1].a.x;
t1=inter(p[i].a,p[j].b,p[k].a,p[k-1].a);
t2=inter(p[i].a,p[j].b,p[k].b,p[k-1].b);
return max(t1.x,t2.x);
}
}
return p[n-1].a.x;
}
int main()
{
int i,j;
double x,ans;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
{
scanf("%lf%lf",&p[i].a.x,&p[i].a.y);
p[i].b.x=p[i].a.x;
p[i].b.y=p[i].a.y-1;
}
ans=p[1].a.x;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j)
continue;
x=work(i,j);
if(x-ans>eps)
ans=x;
}
if(fabs(ans-p[n-1].a.x)<eps)
printf("Through all the pipe.\n");
else
printf("%.2f\n",ans);
}
return 0;
}