Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

asdfasdfasdfasdfasdfasdfa

Posted by zhangxiao1124 at 2008-05-12 16:04:48 on Problem 2966
/*
	一开始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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator