首页 > 代码库 > 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 直线和线段相交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。