「JZOJ3856」规避 - 计算几何+路径规划

题目大意

    2014年7月17日，马来西亚航空MH17班机执飞阿姆斯特丹史基浦机场飞往吉隆坡国际机场航线时，在乌克兰靠近俄罗斯边界33,000英尺高空疑受到9K37山毛榉地对空导弹击落坠毁。事件发生后，汉莎航空、法国航空、土耳其航空、俄罗斯洲际航空、达美航空、英国航空、俄罗斯航空、印度航空、捷特航空和荷兰皇家航空开始禁止班机进入乌克兰东部或全境领空范围。美国航空公司的班机禁止在乌克兰境内飞行，同时UTair航空、意大利航空和维珍航空也宣布他们的班机将会重新规划航行的路线。英国交通部已经要求该国的班机不要进入乌克兰领空范围。中国民用航空局已要求国内航空公司所有飞越乌克兰的航班绕飞。
    作为相关负责人，你需要根据实际情况规划航线规避不安全地区，包括战争区域、危险天气、火山灰和外星人入侵……等。每个不安全区域被标记为一个凸多边形，每个凸多边形相离，你需要规划一条从指定起点到指定终点的航线，要求航线不得进入不安全区域，输出它的最短长度。为了你的方便，起点和终点都是多边形的顶点。

---

题目分析

比较简单的路径规划问题。
显然会在端点处改变路径方向。
将凸多边形的端点提出来两两建边，若不与其他的边相交即可连边。
注意凸多边形外部的边需要连起来。

考试的时候写了非规范相交，惨遭卡常。
因为本题点不重复，路径可以切成合法的两段，故可以将规范相交判断的$\lt0$符号改为$\le0$即可，不需要判断非规范相交。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define DEBUG printf("Passing [%s] in LINE %d...\n",__FUNCTION__,__LINE__)

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=305;

const double eps=1e-8;
int dcmp(double x) {
	if(fabs(x)<eps)return 0;
	else if(x<0)return -1;
	else return 1;
}

struct Point {
	double x,y;
	Point() {}
	Point(double _x,double _y):x(_x),y(_y) {}
	Point operator - (const Point& a) const {
		return Point(a.x-x,a.y-y);
	}
	bool operator == (const Point& b) const {
		return dcmp(x-b.x)==0&&dcmp(y-b.y)==0;
	}
} p[maxn];

typedef Point Vector; 

double Dist(Point a,Point b) { 
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

struct Segment {
	Point a,b;
	Segment() {}
	Segment(Point _a,Point _b):a(_a),b(_b) {}
} l[maxn];

double Dot(Vector a,Vector b) {
	return a.x*b.x+a.y+b.y;
}

double Cross(Vector a,Vector b) {
	return a.x*b.y-b.x*a.y;
}

bool Segment_Intersection(Point a1,Point a2,Point b1,Point b2) { 
	double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
	return dcmp(c1)*dcmp(c2)<=0&&dcmp(c3)*dcmp(c4)<=0;
}

struct Edge {
	int from,to;
	double dist;
};

int n,m,s,t,vst[maxn],tmp[maxn],cnt=0;
double dist[maxn];
vector<Edge>edges[maxn];

void AddEdge(int x,int y,double v) {
	edges[x].push_back((Edge) {x,y,v});
}

struct HeapNode {
	double d;
	int u;
	bool operator < (const HeapNode& b) const {
		return d>b.d;
	}
};

void Dijkstra(int s) {
	priority_queue<HeapNode>Q;
	for(int i=1; i<=cnt; i++)dist[i]=1e18;
	Q.push((HeapNode) {
		0,s
	});
	dist[s]=0;
	while(!Q.empty()) {
		int Now=Q.top().u;
		Q.pop();
		if(vst[Now])continue;
		vst[Now]=1;
		for(int i=0; i<edges[Now].size(); i++) {
			Edge& e=edges[Now][i];
			int Next=e.to;
			if(dist[Next]>dist[Now]+e.dist) {
				dist[Next]=dist[Now]+e.dist;
				Q.push((HeapNode) {
					dist[Next],Next
				});
			}
		}
	}
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++) {
		m=Get_Int();
		int first=cnt+1,last=0;
		tmp[first]=cnt;
		for(int j=1; j<=m; j++) {
			int x=Get_Int(),y=Get_Int();
			p[++cnt]=Point(x,y);
			if(last) {
				l[cnt-1]=Segment(p[cnt],p[last]);
				tmp[cnt]=tmp[first];
				AddEdge(cnt,last,Dist(p[cnt],p[last]));
				AddEdge(last,cnt,Dist(p[last],p[cnt]));
			}
			last=cnt;
		}
		l[cnt]=Segment(p[cnt],p[first]);
		AddEdge(cnt,first,Dist(p[cnt],p[first]));
		AddEdge(first,cnt,Dist(p[first],p[cnt]));
	}
	for(int i=1; i<=cnt; i++)
		for(int j=1; j<=tmp[i]; j++) {
			bool bj=1;
			for(int k=1; k<=cnt; k++) {
				if(l[k].a==p[i]||l[k].b==p[i]||l[k].a==p[j]||l[k].b==p[j])continue;
				if(Segment_Intersection(p[i],p[j],l[k].a,l[k].b)) {
					bj=0;
					break;
				}
			}
			if(!bj)continue;
			AddEdge(i,j,Dist(p[i],p[j]));
			AddEdge(j,i,Dist(p[i],p[j]));
		}
	s=Get_Int();
	t=Get_Int();
	Dijkstra(s);
	printf("%0.4lf\n",dist[t]);
	return 0;
}