[BZOJ1137][POI2009][半平面交]wsp岛屿

BZOJ1137

随便画个图就发现是半平面交
但是有$n^2$n2条边，不需要都取，因为是凸包，按顺序给出的点，所以对于一个点出发的所有边只需要考虑终点编号最大的边就行了，开vector防止炸空间

upd 5 min later：
本校OJ挂掉了，因为没加特判，如果1-n的路没被控制就直接走了

Code:

#include<bits/stdc++.h>
#define eps 1e-9
#define db double
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=1e5+5;
int n,m,tot;
struct point{
	db x,y;
	point(){}
	point(db _x,db _y): x(_x),y(_y) {}
	friend inline point operator - (const point &a,const point &b) {return point(a.x-b.x,a.y-b.y);}
	friend inline db operator * (const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
	inline db dis() {return sqrt(x*x+y*y);}
}p[N];
struct line{
	point a,b;
	db k;
	line(){}
	line(point _a,point _b): a(_a),b(_b){}
}l[N];
inline int sign(double x){return (x>eps)-(x<-eps);}
inline bool operator < (const line &a,const line &b){
	int t=sign(a.k-b.k);
	if(t) return t<0;
	else return (b.b-a.a)*(b.a-a.a)>=0;
}
vector<int>no[N];
inline point insert(line x,line y){
	db k1=(x.b-y.a)*(x.a-y.a);
	db k2=(x.a-y.b)*(x.b-y.b);
	db t=k1/(k1+k2);
	return point(y.a.x+(y.b.x-y.a.x)*t,y.a.y+(y.b.y-y.a.y)*t);
}
inline bool ok(line z,line x,line y){
	point q=insert(x,y);
	return (z.a-q)*(z.b-q)<eps;
}
db ans=0.0;
inline void half(){
    for(int i=1;i<=tot;i++) l[i].k=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
    sort(l+1,l+tot+1); m=0;
    for(int i=1;i<=tot;i++){
        if(i==1 || sign(l[i].k-l[i-1].k)) ++m;
        l[m]=l[i];
    }
    int L=1,R=2;
    for(int i=3;i<=m;i++){
        while(L<R && ok(l[i],l[R-1],l[R])) --R;
        while(L<R && ok(l[i],l[L],l[L+1])) ++L;
        l[++R]=l[i];
    }
    while(L<R-1 && ok(l[R],l[L],l[L+1])) ++L;
    while(L<R-1 && ok(l[L],l[R-1],l[R])) --R;
    ans=-(p[n]-p[1]).dis();
	tot=0;
	l[++R]=l[L];
    for(int i=L;i<R;++i) p[++tot]=insert(l[i],l[i+1]);
    for(int i=1;i<tot;i++) ans+=(p[i+1]-p[i]).dis();
    ans+=(p[1]-p[tot]).dis();
}
int main(){
	bool f=1;
	n=read(),m=read();
    for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        no[min(x,y)].push_back(max(x,y));
        if(x==1 && y==n) f=0;
    	if(x==n && y==1) f=0;
	}
	if(f) {printf("%.9lf",(p[n]-p[1]).dis());return 0;}
    for(int i=1;i<=n;i++){
        if(no[i].size()) sort(no[i].begin(),no[i].end()); 
        int t=no[i].size()-1,use=n;
        while(t>=0 && no[i][t]==use) --use,--t;
        if(use>i) l[++tot]=line(p[use],p[i]);
    }
	l[++tot]=line(p[1],p[n]);
    half();
    printf("%.9lf",ans);
	return 0;
}