锐客网

  1. 首页 > it技术 > >

bzoj|bzoj1137 [POI2009]Wsp 岛屿 半平面交

bzoj半平面交

【bzoj|bzoj1137 [POI2009]Wsp 岛屿 半平面交】题目大意：
有一个n个点的凸多边形，任意两个点之间有一条笔直的路径，可以在路径相交的时候换路。
现在有m条路不能走了，问从点1走到点n的最短路是多少。
题目分析：
这道题其实是让求一个剩余路的半平面交的周长（这到底是怎么想到的orz）。
但是路有n^2条，但是对于一个点，最前面的一条边可以把后面的所有边都弹掉，所以后面那些边都没有用了，只加最前面的一条边就可以了，于是就变成边数就变成了n。
把n到1这条加进来，在统计答案的时候再把这条边减去即可。
代码如下：

#include #include #include #define N 1200000 using namespace std; const double eps=1e-7; inline double sqr(double x) { return x*x; } int n,m,top; pair l[N]; int tmp[N]; struct point{ double x,y; point(){} point(double x,double y):x(x),y(y){} point operator + (const point &c) const { return point(x+c.x,y+c.y); } point operator - (const point &c) const { return point(x-c.x,y-c.y); } double operator * (const point &c) const { return x*c.y-y*c.x; } double operator | (const point &c) const { return sqrt(sqr(x-c.x)+sqr(y-c.y)); } point operator * (const double &c) const { return point(x*c,y*c); } }b[N],h[N]; struct line{ point p,v; double alpha; line(){} line(point a,point b):p(a),v(b-a) { alpha=atan2(v.y,v.x); } bool operator < (const line &c) const { return alpha=0; } double half_plane_intersection() { sort(a+1,a+1+top); int l=1,r=1; for(int i=1; i<=top; i++) { while(r-l>=2 && !onleft(p[r-1]^p[r-2],a[i])) r--; if(r-l>=1 && fabs(p[r-1].v*a[i].v)<=0) p[r-1]=onleft(a[i].p,p[r-1])?a[i]:p[r-1]; else p[r++]=a[i]; } for(; ; ) { if(r-l>=2 && !onleft(p[r-1]^p[r-2],p[l])) r--; else if(r-l>=2 && !onleft(p[l]^p[l+1],p[r-1])) l++; else break; } p[r]=p[l]; for(int i=l; il[i].second) swap(l[i].first,l[i].second); } sort(l+1,l+1+m); for(int i=1; i<=n; i++) tmp[i]=1; for(int i=1; i<=m; i++) if(tmp[l[i].second]==l[i].first) tmp[l[i].second]++; if(tmp[n]==1) { printf("%lf",b[1]|b[n]); return 0; } for(int i=1; i<=n; i++) if(tmp[i]

    推荐阅读


    上一篇：bzoj|bzoj4241 历史研究 回滚莫队

    下一篇：温情的林爸爸〖林爸爸应该也有过后来的我们吧〗