Description：

一个凸多边形，点按顺序标号为 $1\sim n$ ，给出每个点的坐标，任意两点间都有连线，可以在连线的交点处拐弯，有一些边被封锁，问从 $1$ 到 $n$ 的最短距离。

$1\leqslant n\leqslant 10^5$

Solution：

观察一下性质会发现对于一个点，一定是往比他编号大的点走，那么实际有用的路就只有 $O(n)$ 个了，然后又会发现对于一条可以走的路，他的另一边一定不会被走过，于是这就可以看成很多半平面的半平面交问题，加入半平面 $1\sim n$ ，最后求剩下那个多边形的周长就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

vector<int> g[MAXN];

struct point

{

	double x,y;

}p[MAXN];

point operator + (point a,point b){return (point){a.x + b.x,a.y + b.y};}

point operator - (point a,point b){return (point){a.x - b.x,a.y - b.y};}

point operator * (point a,double k){return (point){a.x * k,a.y * k};}

double cross(point a,point b){return (a.x * b.y - a.y * b.x);}

double angle(point k){return atan2(k.y,k.x);} 

struct plane

{

	point p,v;

}pl[MAXN],q[MAXN];

const double eps = 1e-8;

bool equal(double a,double b){return (fabs(a - b) <= eps);}

int sign(double k){return (equal(k,0.0) ? 0 : (k < 0 ? -1 : 1));}

bool in(point p,plane k){return (sign(cross(p - k.p,k.v)) >= 0);}

point intersection(plane a,plane b){return b.p + b.v * (cross(a.v,a.p - b.p) / cross(a.v,b.v));}

bool cmp(plane a,plane b){return angle(a.v) < angle(b.v);}

int head,tail;

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

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		scanf("%lf%lf",&p[i].x,&p[i].y);

	}

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		g[a].push_back(b);g[b].push_back(a);

	}

	int pltot = 0;

	for(int i = 1;i <= n;++i)

	{

		sort(g[i].begin(),g[i].end());

		int j,cur;

		for(j = n,cur = g[i].size() - 1;j > i;--j)

		{

			if(j == g[i][cur])--cur;

			else break;

		}

		if(j <= i)continue;

		pl[++pltot] = (plane){p[i],p[j] - p[i]};

	}

	pl[++pltot] = (plane){p[1],p[1] - p[n]};

	sort(pl + 1,pl + 1 + pltot,cmp);

	int tot = 0;

	for(int i = 1;i <= pltot;++i)

	{

		if(tot == 0)pl[++tot] = pl[i];

		else if(!equal(angle(pl[tot].v),angle(pl[i].v)))pl[++tot] = pl[i];

		else if(!in(pl[tot].p,pl[i]))pl[tot] = pl[i];

	}

	q[head = 1] = pl[1];q[tail = 2] = pl[2];

	for(int i = 3;i <= tot;++i)

	{

		while(head < tail && !in(intersection(q[tail],q[tail - 1]),pl[i]))--tail;

		while(head < tail && !in(intersection(q[head],q[head + 1]),pl[i]))++head;

		q[++tail] = pl[i];

	}

	while(head < tail && !in(intersection(q[tail],q[tail - 1]),q[head]))--tail;

	double ans = 0.0;

	for(int i = head;i <= tail - 2;++i)

	{

		ans += dis(intersection(q[i],q[i + 1]),intersection(q[i + 1],q[i + 2]));

	}

	ans += dis(intersection(q[tail],q[head]),intersection(q[head],q[head + 1]));

	ans += dis(intersection(q[head],q[tail]),intersection(q[tail],q[tail - 1]));

	ans -= dis(p[1],p[n]);

	printf("%.8lf\n",ans);

	return 0;

}