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 p新聞熱點
疑難解答
