【POI 2009】岛屿
程序员文章站
2022-04-04 07:58:58
...
Problem
Byteotia 岛屿是一个凸多边形,它的城市按顺时针编号 到 ,第 个城市坐标为 ,任意两个城市之间都有一条笔直的道路相连,道路相交处可以*穿行。
有 条道路被游击队控制了,不能走,但是可以经过这条道路与未被控制的道路的交点。
请求出从城市 到 的最短距离。
数据范围:,。
Solution
注意若两条道路相交,可以从一条道路出发,走到交点直接转弯走。
由于点是顺时针编号的,那对于一个点,最优情况肯定是走到编号最大的能走到的点。(可以用三角形中 来解释。)
那现在我们就把 的边的规模减小到了 。
然后现在可以画一下图,发现最短路就是这些边半平面交的周长,记录下交点算距离即可。
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;
}