题目大意

Byteotia岛屿是一个凸多边形。城市全都在海岸上。按顺时针编号1到n。任意两个城市之间都有一条笔直的道路相连。道路相交处可以自由穿行。有一些道路被游击队控制了，不能走，但是可以经过这条道路与未被控制的道路的交点。问从城市1到n的最短距离。

两条道路相交的话，可以从一条道路出发，走到交点直接转弯走！

两条道路相交的话，可以从一条道路出发，走到交点直接转弯走！

两条道路相交的话，可以从一条道路出发，走到交点直接转弯走！

分析

因为编号是顺时针编号的

所以我们最优一定会选择编号最大的点去走

（记这条边为L

如果走到一个编号较小的点

最终目标还是要走到n

最后会穿过L这条边

与L相交于D

那还不如我走L这条边走到D这个点转弯呢

）

这样剩下的边数就从\(O(n^2)\)变成\(O(n)\)了

可以发现最短路是半平面交

注意

1.被控制的边有重边

2.找最大可走编号点时注意边界

3.注意半平面交退化的特殊情况要特判

solution

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef double db;const int M=100007;inline int rd(){ int x=0;bool f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=0; for(;isdigit(c);c=getchar()) x=x*10+c-48; return f?x:-x;}int n,m;struct pt{ db x,y; pt(db xx=0,db yy=0){x=xx;y=yy;}}p[M],a[M];int tot;pt operator +(pt x,pt y){return pt(x.x+y.x,x.y+y.y);}pt operator -(pt x,pt y){return pt(x.x-y.x,x.y-y.y);}pt operator *(pt x,db d){return pt(x.x*d,x.y*d);}pt operator /(pt x,db d){return pt(x.x/d,x.y/d);}db dot(pt x,pt y){return x.x*y.x+x.y*y.y;}db det(pt x,pt y){return x.x*y.y-x.y*y.x;}db len(pt x){return sqrt(dot(x,x));}db dis(pt x,pt y){return len(y-x);}db area(pt x,pt y,pt z){return det(y-x,z-x);}struct line{ pt P,v; line(pt PP=pt(),pt vv=pt()){P=PP;v=vv;}}l[M],s[M];int cnt,top;bool ptleft(pt x,line y){return det(y.v,x-y.P)>=0;}pt inter(line x,line y){ pt u=x.P-y.P; db t=det(u,y.v)/det(y.v,x.v); return x.P+x.v*t;}vector
           
            g[M];bool cc(int x,int y){return x>y;}void hpi(){ top=0; int i; for(i=1;i<=cnt;i++){ while(top>1&&ptleft(inter(s[top-1],s[top]),l[i])) top--; s[++top]=l[i]; } tot=0; for(i=2;i<=top;i++) a[++tot]=inter(s[i],s[i-1]);}int main(){ int i,j,x,y; n=rd(),m=rd(); for(i=1;i<=n;i++){ x=rd(),y=rd(); p[i]=pt(x,y); g[i].push_back(0);//防止下面遍历到最后都找不到边 } for(i=1;i<=m;i++){ x=rd(),y=rd(); if(x>y) swap(x,y); g[x].push_back(y); } for(i=1;i