poj1039(计算几何)线段相交 - c++编程基础

题意：给一个管道求光线能穿到的最大x坐标。

解法：通过旋转光线一定可以使得光线接触一个上点和一个下点。枚举接触的上下点，然后逐一判断光线是否穿过每个拐点面。碰到一个拐点面没有穿过的，则是因为与其左边线段相交，求出直线与线段交点更新答案即可。不想交则说明在前一个拐点已经穿出去了。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPrT6wuujujxwcmUgY2xhc3M9"brush:java;">/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include #include //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-10 const double pi=acos(-1.0); typedef long long LL; const int Max=10100; const int INF=1000000007; struct point { double x,y; } points1[30],points2[30]; int n; int mult(point a,point b,point c) { a.x-=c.x; a.y-=c.y; b.x-=c.x; b.y-=c.y; double tool=a.x*b.y-a.y*b.x; if(abs(tool)<=eps) return 0; if(tool<0) return -1; return 1; } double mult2(point a,point b,point c) { a.x-=c.x; a.y-=c.y; b.x-=c.x; b.y-=c.y; return a.x*b.y-a.y*b.x; } bool OK(point p1,point p2,int i) { return mult(p1,p2,points1[i])*mult(p1,p2,points2[i])<=0; } bool inter(point p1,point p2,point p3,point p4) { if(mult(p1,p2,p3)*mult(p1,p2,p4)<0) return true; return false; } double getx(point p1,point p2,point p3,point p4) { double area1=abs(mult2(p1,p2,p3)),area2=abs(mult2(p1,p2,p4)); return area1/(area1+area2)*p4.x+area2/(area1+area2)*p3.x; } double solve(point p1,point p2) { if(!OK(p1,p2,0)) return points1[0].x; for(int i=1; i