欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【POI 2009】岛屿

程序员文章站 2022-04-04 07:58:58
...

传送门


Problem

Byteotia 岛屿是一个凸多边形,它的城市按顺时针编号 11nn,第 ii 个城市坐标为 (xi,yi)(x_i,y_i),任意两个城市之间都有一条笔直的道路相连,道路相交处可以*穿行。

mm 条道路被游击队控制了,不能走,但是可以经过这条道路与未被控制的道路的交点。

请求出从城市 11nn 的最短距离。

数据范围:3n1053≤n≤10^51m1061≤m≤10^6


Solution

注意若两条道路相交,可以从一条道路出发,走到交点直接转弯走。

由于点是顺时针编号的,那对于一个点,最优情况肯定是走到编号最大能走到的点。(可以用三角形中 c>a+bc>a+b 来解释。)

那现在我们就把 O(n2)O(n^2) 的边的规模减小到了 O(n)O(n)

然后现在可以画一下图,发现最短路就是这些边半平面交的周长,记录下交点算距离即可。


Code

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 1000005
#define eps 1e-8
using namespace std;
int n,m,num;
vector<int>e[N];
double D;
int Sign(double x)  {return (x>eps)?1:((x<-eps)?-1:0);}
struct point{
	double x,y;
	point(){}
	point(double x,double y):x(x),y(y){}
	friend point operator+(const point &a,const point &b)  {return point(a.x+b.x,a.y+b.y);}
	friend point operator-(const point &a,const point &b)  {return point(a.x-b.x,a.y-b.y);}
	friend point operator*(const point &a,double b)  {return point(a.x*b,a.y*b);}
	friend double dot(const point &a,const point &b)  {return a.x*b.x+a.y*b.y;}
	friend double cross(const point &a,const point &b)  {return a.x*b.y-a.y*b.x;}
	friend double dis(const point &a)  {return sqrt(a.x*a.x+a.y*a.y);}
}p[N],inter[N];
struct line{
	point S,T;
	double angle;
	line(){}
	line(point S,point T):S(S),T(T){}
}a[N],l[N],Q[N];
bool operator<(const line &p,const line &q){
	return Sign(p.angle-q.angle)==0?Sign(cross(q.T-p.S,q.S-p.S))>0:Sign(p.angle-q.angle)<0;
}
point Intersection(line a,line b){
	double S1=cross(b.S-a.S,b.T-a.S);
	double S2=cross(b.S-a.T,b.T-a.T);
	double k=S1/(S1-S2);
	return a.S+(a.T-a.S)*k;
}
bool Judge(line a,line b,line c){
	point p=Intersection(a,b);
	return Sign(cross(p-c.S,c.T-c.S))>0;
}
double Solve(){
	int tot=0,sum=0;
	for(int i=1;i<=num;++i)
		if(l[i].angle!=a[tot].angle)
			a[++tot]=l[i];
	int L=1,R=0;
	Q[++R]=a[1],Q[++R]=a[2];
	for(int i=3;i<=tot;++i){
		while(L<R&&Judge(Q[R-1],Q[R],a[i]))  --R;
		while(L<R&&Judge(Q[L+1],Q[L],a[i]))  ++L;
		Q[++R]=a[i];
	}
	while(L<R&&Judge(Q[R-1],Q[R],Q[L]))  --R;
	while(L<R&&Judge(Q[L+1],Q[L],Q[R]))  ++L;
	for(int i=L;i<R;++i)  inter[++sum]=Intersection(Q[i],Q[i+1]);
	inter[0]=inter[++sum]=Intersection(Q[L],Q[R]);
	double ans=0;
	for(int i=1;i<=sum;++i)
		ans+=dis(inter[i]-inter[i-1]);
	return ans-D;
}
int main(){
	int x,y,i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	D=dis(p[1]-p[n]);
	for(i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		if(x>y) swap(x,y);
		e[x].push_back(y);
	}
	for(i=1;i<n;++i){
		sort(e[i].begin(),e[i].end()),j=n;
		while(!e[i].empty()&&e[i].back()==j)  j--,e[i].pop_back();
		if(i==1&&j==n)  return printf("%.9lf",D),0;
		if(j>i)  l[++num]=line(p[j],p[i]);
	}
	l[++num]=line(p[1],p[n]);
	for(i=1;i<=num;++i)  l[i].angle=atan2(l[i].T.y-l[i].S.y,l[i].T.x-l[i].S.x);
	sort(l+1,l+num+1);
	printf("%.9lf",Solve());
	return 0;
}
相关标签: 半平面交