Description

Byteotia島嶼是一個(gè)凸多邊形。城市全都在海岸上。按順時(shí)針編號(hào)1到n。任意兩個(gè)城市之間都有一條筆直的道路相連。道路相交處可以自由穿行。有一些道路被游擊隊(duì)控制了，不能走，但是可以經(jīng)過(guò)這條道路與未被控制的道路的交點(diǎn)。問(wèn)從城市1到n的最短距離。

Input

第一行正整數(shù)n m表示城市數(shù)和被控制的島嶼數(shù)（3≤n≤10^5 1≤m≤10^6）接下來(lái)n行每行兩個(gè)整數(shù)x y表示每個(gè)城市的坐標(biāo)。（|x|,|y|≤10^6）接下來(lái)m行描述一條不能走的道路（起點(diǎn)和終點(diǎn)）。數(shù)據(jù)保證有解。

Output

輸出一個(gè)實(shí)數(shù)，最短距離，誤差10^-5以內(nèi)均算正確。

Sample Input

Sample Output

HINT

Source

鳴謝 vfleaking

題解：半平面交

這道題一看數(shù)據(jù)范圍就知道一定不能用普通的最短路做。

所以我們考慮半平面交。最短的路徑應(yīng)該就是所有可以通行的直線交出的凸包的周長(zhǎng)，但是O(n(n-1)/2)做不了半平面交。其實(shí)可以發(fā)現(xiàn)與i相連的有用的直線就是i能到達(dá)的最遠(yuǎn)的點(diǎn)與i的連線。

然后我們加入直線1->n，算答案的時(shí)候再減掉即可。

#include<iostream>  #include<cstring>  #include<cstdio>  #include<algorithm>  #include<cmath>  #define N 500003 #define eps 1e-8  #define inf 1000000000using namespace std;  int n,m,v[N],pos[N],head,tail,cnt;  struct data{      int x,y;  }e[N*4];  struct vector{      double x,y;      vector(double X=0,double Y=0) {          x=X,y=Y;      };  }a[N],p[N],poly[N]; vector Operator-(vector a,vector b){      return vector (a.x-b.x,a.y-b.y);  }  vector operator+(vector a,vector b){      return vector (a.x+b.x,a.y+b.y);  }  vector operator*(vector a,double val){      return vector (a.x*val,a.y*val);  }   struct line{	vector p,v;	double ang;	line() {		p=vector(); v=vector();	}	line(vector a,vector b){		p=a; v=b-a; ang=atan2(v.y,v.x);	}}l[N],q[N]; bool operator <(line a,line b){	return a.ang<b.ang;}int dcmp(double x){      if (fabs(x)<eps) return 0;      return x<0?-1:1;  }  double cross(vector a,vector b){      return a.x*b.y-a.y*b.x;  }  vector glt(line a,line b)  {      vector u=a.p-b.p;    double t=cross(b.v,u)/cross(a.v,b.v);      return a.p+a.v*t;  }  void init(){	p[1]=vector(-inf,-inf); p[2]=vector(inf,-inf); p[3]=vector(inf,inf); p[4]=vector(-inf,inf);	l[++m]=line(p[4],p[1]); 	l[++m]=line(p[3],p[4]);	l[++m]=line(p[2],p[3]);	l[++m]=line(p[1],p[2]);}bool Onleft(line a,vector w){	return cross(a.v,(w-a.p))>=-eps;}void halfpins(){	sort(l+1,l+m+1);	head=tail=1; q[1]=l[1];	for (int i=2;i<=m;i++) {		while (head<tail&&!Onleft(l[i],p[tail-1])) --tail;		while (head<tail&&!Onleft(l[i],p[head])) head++;		q[++tail]=l[i];		if (fabs(cross(q[tail].v,q[tail-1].v))<eps) {			--tail;			if (Onleft(q[tail],l[i].p)) q[tail]=l[i];		}		if (head<tail) 		 p[tail-1]=glt(q[tail-1],q[tail]); 	} 	while (head<tail&&!Onleft(q[head],p[tail-1])) --tail; 	if (tail-head<=1) return; 	p[tail]=glt(q[tail],q[head]); 	for (int i=head;i<=tail;i++) poly[++cnt]=p[i]; 	poly[cnt+1]=poly[1];}int cmp(data a,data b){      return a.x<b.x||a.x==b.x&&a.y>b.y;  }  double get_len(vector a)  {       return sqrt(a.x*a.x+a.y*a.y);  }  int main()  {      freopen("a.in","r",stdin);      //freopen("my.out","w",stdout);    scanf("%d%d",&n,&m);      for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);      for (int i=1;i<=m;i++) {       scanf("%d%d",&e[i].x,&e[i].y);       if (e[i].x>e[i].y) swap(e[i].x,e[i].y);      }      sort(e+1,e+m+1,cmp);        for (int i=1;i<=m;i++) pos[e[i].x]=max(pos[e[i].x],i);      for (int i=1;i<=n;i++) {          if (pos[i]<pos[i-1]) {              if (i!=n) v[i]=n;              continue;          }          if (e[pos[i-1]+1].y!=n) {              v[i]=n;              continue;          }          for(int j=pos[i-1]+1;j<=pos[i];j++)           if (e[j].y!=e[j+1].y+1||j+1>pos[i]) {              v[i]=e[j].y-1;              break;           }          if (v[i]<=i) v[i]=0;      }       if (v[1]==n) {    	PRintf("%.5lf/n",get_len(a[n]-a[1]));    	return 0;	}	m=0; init();    l[++m]=line(a[1],a[n]);    for (int i=1;i<=n;i++)       if (v[i]) l[++m]=line(a[v[i]],a[i]);    halfpins();    double ans=0;      for (int i=1;i<=cnt;i++) 	 ans+=get_len(poly[i%cnt+1]-poly[(i+1)%cnt+1]);    printf("%.5lf/n",ans-get_len(a[n]-a[1]));  }