| ||||||||||
| 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