http://poj.org/PRoblem?id=1039 题意：给出一个曲折的管道，求出光线能够到达的管道的最远点的横坐标。 思路：能够到达最远点的直线必然通过管道的一个上管道壁的折点和一个下管道壁的折点，枚举所有的这样的折点，求出最远能够到达的地方的横坐标。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;int n;double maxx= -(1<<30);const int maxn = 1e6+10;const double precision = 1e-3;const double inf = (1<<30);struct point{ double x; double y;}up[maxn],down[maxn];int dblcmp(double p){ if(fabs(p)<precision) return 0; return p>0?1:-1;}double det(double x1,double y1,double x2,double y2){ return x1*y2-x2*y1;}double cross(point A,point B,point P){ return det(B.x-A.x , B.y-A.y , P.x-A.x , P.y-A.y);}bool segcross(point A,point B,point C,point D){ return (dblcmp(cross(A,B,C)) * dblcmp(cross(A,B,D)) <= 0);}double intersection(point A,point B,point C,point D){ double area1=cross(A,B,C); double area2=cross(A,B,D); int c=dblcmp(area1); int d=dblcmp(area2); if(c*d<0) return (area2*C.x - area1*D.x)/(area2-area1); if(c*d==0) if(c==0) return C.x; else return D.x; return -inf;}void init(){ maxx = -(1<<30); for(int i = 1;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; }}void sov(){ bool flag=false; int k; for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++) if(i!=j){ for(k=1; k <= n;k++) if(!segcross(up[i],down[j],up[k],down[k])) break; if(k > n){ flag=true; break; } else{ if(k < max(i,j)) continue; double temp1=intersection(up[i],down[j],up[k],up[k-1]),temp2 = intersection(up[i],down[j],down[k],down[k-1]); maxx = max(max(temp1,maxx),temp2); } } if(flag) break; } if(flag) printf("Through all the pipe./n"); else{ printf("%.2f/n",maxx); }}int main(){ while(~scanf("%d",&n)&&n){ init(); sov(); } return 0;}新闻热点
疑难解答
