首页 > 代码库 > POJ 1039 直线和线段相交

POJ 1039 直线和线段相交

题意:

题意很好理解,从左边射过来的光线,最远能经过管道到右边多少距离。

分析:

光线一定经过一个上端点和一个下端点,这一点很容易想到。然后枚举上下端点即可

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define eps 1e-8#define INF 1e9#define OK sgn(tmp-lx1)>0 && sgn(tmp-lx2<0)using namespace std;typedef struct Point{    double x,y;    Point() {};    Point(double xx,double yy)    {        x=xx;        y=yy;    }} Vector;struct Line{    Point p,q;    Line() {};    Line(Point pp,Point qq)    {        p=pp;        q=qq;    }};int sgn(double x){    if(fabs(x)<eps) return 0;    return x<0? -1:1;}double crs_prdct(Vector a,Vector b){    return a.x*b.y-b.x*a.y;}Vector operator - (Point a,Point b){    return Vector(a.x-b.x,a.y-b.y);}double cross_x(Point p1,Point p2,Point p3,Point p4){    double k1=(p1.y-p2.y)/(p1.x-p2.x);    double k2=(p3.y-p4.y)/(p3.x-p4.x);    return (k1*p1.x-k2*p3.x-p1.y+p3.y)/(k1-k2);}double get_y(Point p,Point q,double x){    return (p.y-q.y)/(p.x-q.x)*(x-p.x)+p.y;}//判断直线和线段相交bool Seg_inter_line(Line l1,Line l2) //判断直线l1和线段l2是否相交,<0是把交于线段端点处看做不相交{    return sgn(crs_prdct(l2.p-l1.q,l1.p-l1.q))*sgn(crs_prdct(l2.q-l1.q,l1.p-l1.q)) < 0;}const int maxn=30;Point Up[maxn],Dw[maxn];int main(){//    freopen("in.txt","r",stdin);    int n;    while(scanf("%d",&n),n)    {        double x,y;        for(int i=0; i<n; i++)        {            scanf("%lf%lf",&x,&y);            Up[i]=Point(x,y);            Dw[i]=Point(x,y-1);        }        double ans=Up[0].x;        for(int i=0; i<n; i++)        {            for(int j=0; j<n; j++)            {                if(i==j) continue;                for(int k=0; k<n-1; k++)                {                    if(Seg_inter_line(Line(Up[i],Dw[j]),Line(Up[k],Up[k+1])))                    {                        ans=max(ans,cross_x(Up[i],Dw[j],Up[k],Up[k+1]));                        break;                    }                    if(Seg_inter_line(Line(Up[i],Dw[j]),Line(Dw[k],Dw[k+1])))                    {                        ans=max(ans,cross_x(Up[i],Dw[j],Dw[k],Dw[k+1]));                        break;                    }                    double t=get_y(Up[i],Dw[j],(Up[k].x+Up[k+1].x)/2);                    if(t>(Up[k].y+Up[k+1].y)/2 || t<(Dw[k].y+Dw[k+1].y)/2)                    {                        ans=max(ans,Up[k].x);                        break;                    }                    if(k==n-2) ans=Up[n-1].x;                }            }        }        if(sgn(ans-Up[n-1].x)==0) printf("Through all the pipe.\n");        else printf("%.2f\n",ans);    }    return 0;}

 

POJ 1039 直线和线段相交