bzoj 1137: [POI2009]Wsp 岛屿 （半平面交）

Description

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

Input

第一行正整数n m表示城市数和被控制的岛屿数（3≤n≤10^5 1≤m≤10^6）接下来n行每行两个整数x y表示每个城市的坐标。（|x|,|y|≤10^6）接下来m行描述一条不能走的道路（起点和终点）。数据保证有解。

Output

输出一个实数，最短距离，误差10^-5以内均算正确。

Sample Input

Sample Output

HINT

Source

鸣谢 vfleaking

题解：半平面交

这道题一看数据范围就知道一定不能用普通的最短路做。

所以我们考虑半平面交。最短的路径应该就是所有可以通行的直线交出的凸包的周长，但是O(n(n-1)/2)做不了半平面交。其实可以发现与i相连的有用的直线就是i能到达的最远的点与i的连线。

然后我们加入直线1->n，算答案的时候再减掉即可。

#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]));  }