[BZOJ1137][POI2009]Wsp 島嶼（半平面交）

2019-11-08 03:27:45

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門

題解

這道題路徑的交點處是可以隨意通行的如果1->n是可通行的那么直接走就行了如果不能通行對于每一個點i，找出它能直接走到的編號最大的點，顯然只有這個點是有用的然后從點i向這個點連一條直線，加上n->1這條直線，實際上交出了一個凸多邊形答案即為這個凸多邊形的邊長-1->n的路徑長

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1000005const double eps=1e-9;const double inf=1e7;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}struct data{ int x,y; bool Operator < (const data &a) const { return x<a.x||x==a.x&&y>a.y; }}e[N];struct Vector{ double x,y; Vector(double X=0,double Y=0,double ANG=0) { x=X,y=Y; }};typedef Vector Point;struct Line{ Point p; Vector v; double ang; Line(Point P=Point(0,0),Vector V=Vector(0,0),double ANG=0) { p=P,v=V,ang=atan2(v.y,v.x); } bool operator < (const Line &a) const { return ang<a.ang; }};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 b) {return Vector(a.x*b,a.y*b);}int n,m,cnt,l,r,est[N];double ans;Point pt[N],p[N],poly[N];Line L[N],q[N];bool flag;double Len(Vector a){ return sqrt(a.x*a.x+a.y*a.y);}double Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x;}Point GLI(Point P,Vector v,Point Q,Vector w){ Vector u=P-Q; double t=Cross(w,u)/Cross(v,w); return P+v*t;}bool Onleft(Line m,Point P){ Vector w=P-m.p; return dcmp(Cross(m.v,w))>=0;}void halfp(){ sort(L+1,L+cnt+1); q[l=r=1]=L[1]; for (int i=2;i<=cnt;++i) { while (l<r&&!Onleft(L[i],p[r-1])) --r; while (l<r&&!Onleft(L[i],p[l])) ++l; q[++r]=L[i]; if (dcmp(Cross(q[r].v,q[r-1].v))==0) { --r; if (Onleft(q[r],L[i].p)) q[r]=L[i]; } if (l<r) p[r-1]=GLI(q[r-1].p,q[r-1].v,q[r].p,q[r].v); } while (l<r&&!Onleft(q[l],p[r-1])) --r; cnt=0; if (r-l<=1) return; p[r]=GLI(q[r].p,q[r].v,q[l].p,q[l].v); for (int i=l;i<=r;++i) poly[++cnt]=p[i];}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%lf%lf",&pt[i].x,&pt[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); if (e[i].x==1&&e[i].y==n) flag=1; } if (!flag) { ans=Len(pt[1]-pt[n]);