http://poj.org/PRoblem?id=1039 題意：給出一個(gè)曲折的管道，求出光線能夠到達(dá)的管道的最遠(yuǎn)點(diǎn)的橫坐標(biāo)。 思路：能夠到達(dá)最遠(yuǎn)點(diǎn)的直線必然通過(guò)管道的一個(gè)上管道壁的折點(diǎn)和一個(gè)下管道壁的折點(diǎn)，枚舉所有的這樣的折點(diǎn)，求出最遠(yuǎn)能夠到達(dá)的地方的橫坐標(biāo)。
#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新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
