1137: [POI2009]Wsp 岛屿

#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>

const int len(100000);
const double eps(1e-8);
struct Coor//向量或点 
{
    double x,y;
    Coor(){};
    Coor(double a,double b):x(a),y(b){};
inline Coor operator +(const Coor&a)const{return Coor(x+a.x,y+a.y);}
inline Coor operator -(const Coor&a)const{return Coor(x-a.x,y-a.y);}
inline Coor operator *(const double&k)const{return Coor(x*k,y*k);}
inline Coor operator /(const double&k)const{return Coor(x/k,y/k);}
}pr[len+10],ie[len+10];int tot;
double dot(Coor a,Coor b){return a.x*b.x+a.y*b.y;}//点积 
double cross(Coor a,Coor b){return a.x*b.y-a.y*b.x;}//叉积
struct Line
{
    Coor a,b;//直线上两个点a->b,钦点半平面交均保留向量左手方向。 
    double angle;
    Line(){};
    Line(Coor A,Coor B,double a):a(A),b(B),angle(a){};
    Coor intersect(Line &B)
    {
        double s1=cross(B.a-a,B.b-a),s2=cross(B.b-b,B.a-b);//面积的方向 
        return a+(b-a)*s1/(s1+s2);
    }
    void getAngle(){angle=atan2(b.y-a.y,b.x-a.x);}
}L[len+10];int up;
int n,m,x,y;long double ans;
std::vector<int>Edge[len+10];
void swap(int &x,int &y){x^=y,y^=x,x^=y;}
int dcmp(double x){return x<-eps?-1:x>eps;}
bool cmp(Line A,Line B)
{
    double c=A.angle-B.angle;
    int d=dcmp(c);
    if(d)return d>0;//逆时针,事实证明这里正着反着都一样。 
    c=cross(A.b-A.a,B.b-A.a);//保留左手方向 
    return c<-eps;
}
bool jud(Line p1,Line p2,Line p3)
{
    Coor p=p1.intersect(p2);
    double c=cross(p3.b-p3.a,p-p3.a);
    return dcmp(c)<0;
}
void deal()
{
    int _up=1;
    for(int i=2;i<=up;i++)if(dcmp(L[i-1].angle-L[i].angle))L[++_up]=L[i];
    up=_up;
}
long double sqr(long double x){return x*x;}
long double dis(Coor A,Coor B)
{
    return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
}
int que[len+10],head,tail;
void SI()
{
    std::sort(L+1,L+1+up,cmp);//排序可能会打乱顺序 
    deal();
    que[1]=1;que[2]=2;head=1;tail=2;
    for(int i=3;i<=up;i++)
    {
        while(head<tail && jud(L[que[tail-1]],L[que[tail]],L[i]))
            tail--;
        while(head<tail && jud(L[que[head+1]],L[que[head]],L[i]))
            head++;
        que[++tail]=i;
    }
    while(head<tail-1 && jud(L[que[tail-1]],L[que[tail]],L[que[head]]))
        tail--;
    while(head+1<tail && jud(L[que[head+1]],L[que[head]],L[que[tail]]))
        head++;
    que[tail+1]=que[head];
    for(int i=head;i<=tail;i++)ie[++tot]=L[que[i]].intersect(L[que[i+1]]);
    ie[tot+1]=ie[1];
    for(int i=1;i<=tot;i++)ans+=dis(ie[i],ie[i+1]);
    ans-=dis(pr[1],pr[n]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lf %lf",&pr[i].x,&pr[i].y);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        if(x>y)swap(x,y);
        Edge[x].push_back(y);
    }
    for(int i=1,j;i<n;i++)
    {
        std::sort(Edge[i].begin(),Edge[i].end());
        j=n;
        while(Edge[i].size()&&Edge[i].back()==j&&j>i)
        j--,Edge[i].pop_back();
        if(j>i)L[++up]=Line(pr[j],pr[i],0);//逆时针
        if(i==1&&j==n)ans=dis(pr[1],pr[n]);
    }
    if(ans){printf("%.10Lf\n",ans);return 0;}
    L[++up]=Line(pr[1],pr[n],0);
    for(int i=1;i<=up;i++)L[i].getAngle();
    SI();
    printf("%.10Lf\n",ans);
    return 0;
}