| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
asdfasdfasdfasdfasdfasdfa/* 一开始Wa了 后来改了两处才AC Special_Judge的意思就是特判两点直接可以连 Special_Build就是对起点和终点在多边形点上或边上时特殊处理 其他好像没什么了 */ #include<iostream> #include<math.h> using namespace std; #define maxn 200 #define Inf 1e20 #define pi 3.1415926535898 #define alpha pi/11.0 #define sqr(x) ((x)*(x)) #define zero 1e-8 struct Point { double x,y; void Rotate() { double tx=x*cos(alpha)-y*sin(alpha); double ty=y*cos(alpha)+x*sin(alpha); x=tx,y=ty; } void Readin() { scanf("%lf%lf",&x,&y); Rotate(); } } a,b,p[maxn]; int n; double d[maxn][maxn]; void Init() { a.Readin(); b.Readin(); scanf("%d",&n); for (int i=0; i<n; i++) p[i].Readin(); p[n]=p[0]; } inline double Dist(Point a,Point b) { return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } inline int Sign(double x) { if (fabs(x)<zero) return 0; return (x>0)?1:-1; } inline int Cpt(double x_1,double y_1,double x_2,double y_2) { return Sign(x_1*y_2-x_2*y_1); } inline int Dpt(double x_1,double y_1,double x_2,double y_2) { return Sign(x_1*x_2+y_1*y_2); } inline double Unstrict_Cross(Point a,Point b,Point c,Point d) { int v=Cpt(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y)*Cpt(b.x-a.x,b.y-a.y,d.x-a.x,d.y-a.y); int u=Cpt(d.x-c.x,d.y-c.y,a.x-c.x,a.y-c.y)*Cpt(d.x-c.x,d.y-c.y,b.x-c.x,b.y-c.y); return u<=0 && v<=0; } inline double Strict_Cross(Point a,Point b,Point c,Point d) { int v=Cpt(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y)*Cpt(b.x-a.x,b.y-a.y,d.x-a.x,d.y-a.y); int u=Cpt(d.x-c.x,d.y-c.y,a.x-c.x,a.y-c.y)*Cpt(d.x-c.x,d.y-c.y,b.x-c.x,b.y-c.y); return u<0 && v<0; } bool In_Segment(Point c,Point a,Point b) { return !Cpt(c.x-a.x,c.y-a.y,c.x-b.x,c.y-b.y) && Dpt(c.x-a.x,c.y-a.y,c.x-b.x,c.y-b.y)<=0 ; } bool In_Polygon(Point a) { int res=0; for (int i=0; i<n; i++) if (min(p[i].x,p[i+1].x)<a.x && max(p[i].x,p[i+1].x)>a.x) { double y=(p[i].x*p[i+1].y-p[i].y*p[i+1].x)-(p[i+1].y-p[i].y)*a.x; y/=(p[i].x-p[i+1].x); if (y<a.y) res++; } return res%2; } //============================================================================ bool Legal(Point a,Point b,int vertex) { int res=0; for (int i=0; i<n; i++) if (Unstrict_Cross(p[i],p[i+1],a,b)) res++; for (int i=0; i<n; i++) if (In_Segment(p[i],a,b)) res--; if (res==vertex) { if (vertex==1) return true; Point c; c.x=(a.x+b.x)*0.5; c.y=(a.y+b.y)*0.5; return !In_Polygon(c); } return false; } //================================================================== void Special_Build_1() { for (int i=0; i<n; i++) if (!Sign(p[i].x-a.x) && !Sign(p[i].y-a.y)) { d[n][i]=d[i][n]=0.0; return ; } int v=1; for (int i=0; i<n; i++) if (In_Segment(a,p[i],p[i+1])) { v=2; break; } for (int i=0; i<n; i++) if (Legal(a,p[i],v)) d[n][i]=d[i][n]=Dist(p[i],a); } void Special_Build_2() { for (int i=0; i<n; i++) if (!Sign(p[i].x-b.x) && !Sign(p[i].y-b.y)) { d[n+1][i]=d[i][n+1]=0.0; return ; } int v=1; for (int i=0; i<n; i++) if (In_Segment(b,p[i],p[i+1])) { v=2; break; } for (int i=0; i<n; i++) if (Legal(b,p[i],v)) d[n+1][i]=d[i][n+1]=Dist(p[i],b); } void Build() { for (int i=0; i<n+2; i++) for (int j=0; j<n+2; j++) d[i][j]=Inf; Special_Build_1(); Special_Build_2(); for (int i=0; i<n-1; i++) for (int j=i+1; j<n; j++) { if (i+1==j || i==0 && j==n-1) d[i][j]=d[j][i]=Dist(p[i],p[j]); else if (Legal(p[i],p[j],2)) d[i][j]=d[j][i]=Dist(p[i],p[j]); } } double g[maxn]; bool v[maxn]; void Dijkstra() { memset(v,0,sizeof(v)); for (int i=0; i<n+2; i++) g[i]=d[n][i]; v[n]=true,g[n]=0.0; while (1) { double min_d=2*Inf; int p; for (int i=0; i<n+2; i++) if (!v[i] && g[i]<min_d) { min_d=g[i]; p=i; } if (p==n+1) { printf("%.4lf\n",g[n+1]); return; } v[p]=true; for (int i=0; i<n+2; i++) if (!v[i]) g[i]<?=g[p]+d[p][i]; } } bool Special_Judge() { int r[3]; for (int i=0; i<n; i++) { int rr=Cpt(b.x-a.x,b.y-a.y,p[i].x-a.x,p[i].y-a.y)+1; r[rr]++; } if (!r[0] || !r[2]) { printf("%.4lf\n",Dist(a,b)); return true; } for (int i=0; i<n; i++) if (Unstrict_Cross(a,b,p[i],p[i+1])) return false; printf("%.4lf\n",Dist(a,b)); return true; } int main() { Init(); if (Special_Judge()) return 0; Build(); Dijkstra(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator