首页 > 代码库 > POJ 1039

POJ 1039

2024-07-14 10:05:49   219人阅读

一条直线，必定可以通过旋转和平移使得它和一个上顶点一下顶点相切，这样的直线是最优的。因为这样能确定了直线所能到达的最远X。这样的两个顶点就规定了它的上下界，

所以，枚举上下顶点，注意判断是否能到达入口处。只需判断直线是否与每个横切面的直线都有相交。

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const double eps=0.00000001;struct point{	double x,y;}up[30],dp[30];struct edge{	point start,end;}Line;int n;double longest;int dpcmp(double h){	if(fabs(h)<eps) return 0;	return h>0?1:-1;}bool cross(point a,point b,point c,point d){	double h=(c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);	double j=(d.x-a.x)*(b.y-a.y)-(d.y-a.y)*(b.x-a.x);	int s1=dpcmp(h); int s2=dpcmp(j);	if(s1*s2<0)	return true;	else if(s1*s2==0){		return true;	}	return false;}bool slove(int uper, int down){	int i;	for(i=0;i<n;i++)		if(!cross(Line.start,Line.end,up[i],dp[i])) break;		if(i>=n) {			return true;		}		else if(i<max(uper,down)) return false;		else{			double x1=-90080000,x2=-90080000;			double k1=(Line.end.y-Line.start.y)/(Line.end.x-Line.start.x);			double k2=(up[i].y-up[i-1].y)/(up[i].x-up[i-1].x);			double k3=(dp[i].y-dp[i-1].y)/(dp[i].x-dp[i-1].x);			if(cross(Line.start,Line.end,up[i-1],up[i]))			x1=(up[i].y-Line.end.y+k1*Line.end.x-k2*up[i].x)/(k1-k2);			if(cross(Line.start,Line.end,dp[i-1],dp[i]))			x2=(dp[i].y-Line.end.y+k1*Line.end.x-k3*dp[i].x)/(k1-k3);			longest=max(longest,max(x1,x2));			return false;		}}int main(){	while(scanf("%d",&n)!=EOF){		if(n==0) break;		longest=-90080000;		for(int i=0;i<n;i++){			scanf("%lf%lf",&up[i].x,&up[i].y);			dp[i]=up[i]; dp[i].y=dp[i].y-1;		}		bool flag=false;		for(int i=0;i<n;i++){			for(int j=0;j<n;j++)			if(i!=j){				Line.start=up[i]; Line.end=dp[j];				if(slove(i,j)){					flag=true;					break;				}			}			if(flag)			break;		}		if(flag) printf("Through all the pipe.\n");		else printf("%.2f\n",longest);	}	return 0;}

　　


联系
我们