首页 > 代码库 > 最短路+线段交 POJ 1556 好题
最短路+线段交 POJ 1556 好题
1 // 最短路+线段交 POJ 1556 好题 2 // 题意:从(0,5)到(10,5)的最短距离,中间有n堵墙,每堵上有两扇门可以通过 3 // 思路:先存图。直接n^2来暴力,不好写。分成三部分,起点 终点和之间的点:中间点之间:起点和终点的距离 4 // n最大为18所以直接n^3最短路 5 6 7 #include <cstdio> 8 #include <cstring> 9 #include <iostream> 10 #include <algorithm> 11 #include <map> 12 #include <set> 13 #include <queue> 14 #include <stdlib.h> 15 #include <cmath> 16 using namespace std; 17 typedef long long LL; 18 const double inf = 1e9; 19 const int N = 5000; 20 const double eps = 1e-8; 21 void fre() {freopen("in.txt","r",stdin);} 22 23 int sgn(double x){ 24 if(fabs(x)<eps) return 0; 25 if(x<0) return -1; 26 return 1; 27 } 28 29 struct Point{ 30 double x,y; 31 Point(){} 32 Point(double _x,double _y){ 33 x=_x;y=_y; 34 } 35 Point operator -(const Point &b)const{ 36 return Point(x-b.x,y-b.y); 37 } 38 double operator *(const Point &b)const{ 39 return x*b.x+y*b.y; 40 } 41 double operator ^(const Point &b)const{ 42 return x*b.y-y*b.x; 43 } 44 }; 45 46 struct Line{ 47 Point s,e; 48 Line(){} 49 Line(Point _s,Point _e){ 50 s=_s,e=_e; 51 } 52 }; 53 Line line[N]; 54 double xmult(Point p0,Point p1,Point p2){ 55 return (p1-p0)^(p2-p0); 56 } 57 58 double dist(Point a,Point b){ 59 return sqrt((a-b)*(a-b)); 60 } 61 62 bool inter(Line l1,Line l2){ 63 return max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x)&&max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x)&&max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y)&&max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y)&&sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0&&sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0; 64 } 65 66 double d[100][100]; 67 int main(){ 68 // fre(); 69 int n; 70 while(~scanf("%d",&n)){ 71 if(n==-1) break; 72 // clc(d, 73 for(int i=0;i<=4*n+1;i++){ 74 for(int j=0;j<=4*n+1;j++){ 75 if(i==j) d[i][j]=0; 76 else d[i][j]=inf; 77 } 78 } 79 for(int i=1;i<=n;i++){ 80 double x,y3,y1,y4,y2; 81 scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4); 82 line[i*2-1]=Line(Point(x,y1),Point(x,y2)); 83 line[i*2]=Line(Point(x,y3),Point(x,y4)); 84 } 85 bool flag; 86 for(int i=1;i<=4*n;i++){ 87 flag=true; 88 int cn=(i+3)/4; 89 Point tem; 90 if(i&1) tem=line[(i+1)/2].s; 91 else tem=line[(i+1)/2].e; 92 for(int j=1;j<cn;j++){ 93 if(inter(line[j*2-1],Line(Point(0,5),tem))==false&&inter(line[j*2],Line(Point(0,5),tem))==false){ 94 flag=false; 95 break; 96 } 97 } 98 if(flag) d[0][i]=d[i][0]=dist(Point(0,5),tem); 99 flag=true;100 for(int j=cn+1;j<=n;j++){101 if(inter(line[j*2-1],Line(Point(10,5),tem))==false&&inter(line[j*2],Line(Point(10,5),tem))==false){102 flag=false;103 break;104 }105 }106 if(flag) d[4*n+1][i]=d[i][4*n+1]=dist(Point(10,5),tem);107 }108 flag=true;109 for(int i=1;i<=4*n;i++){110 for(int j=i+1;j<=4*n;j++){111 flag=true;112 Point p1,p2;113 int cn1,cn2;114 cn1=(i+3)/4;115 cn2=(j+3)/4;116 if(i&1) p1=line[(i+1)/2].s;117 else p1=line[(i+1)/2].e;118 if(j&1) p2=line[(j+1)/2].s;119 else p2=line[(j+1)/2].e;120 for(int cn=cn1+1;cn<cn2;cn++){121 if(inter(line[cn*2-1],Line(p1,p2))==false&&inter(line[cn*2],Line(p1,p2))==false){122 flag=false;123 break;124 }125 }126 if(flag) d[i][j]=d[j][i]=dist(p1,p2);127 }128 }129 flag=true;130 for(int i=1;i<=n;i++){131 if(inter(line[i*2-1],Line(Point(0,5),Point(10,5)))==false&&inter(line[i*2],Line(Point(0,5),Point(10,5)))==false){132 flag=false;133 break;134 }135 }136 if(flag) d[0][4*n+1]=d[4*n+1][0]=dist(Point(0,5),Point(10,5));137 for(int i=0;i<=4*n+1;i++){138 for(int j=0;j<=4*n+1;j++){139 for(int k=0;k<=4*n+1;k++){140 if(d[i][k]+d[k][j]<d[i][j]) d[i][j]=d[i][k]+d[k][j];141 }142 }143 }144 printf("%.2f\n",d[0][4*n+1]);145 }146 return 0;147 }
最短路+线段交 POJ 1556 好题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。