半平面的交,二分法(离海最远的点,LA 3890)

    xiaoxiao2021-03-26  3

    太菜啦,这都不会。。。

    点到海的距离是点到海的最小距离,然后想让这个值最大。想到了啥?不就是应该用二分吗?太菜了。

    把这个n个点的凸多边形的岛看做n个半平面的交。

    二分距离,检查是否存在一个距离海这么远的点,具体做法就是将所有半平面对应的直线往左边移动这么远,然后看看交是否为空即可。

    代码

    #include<bits/stdc++.h> using namespace std; const int maxn = 110; struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y){} }; typedef Point Vector; const double eps = 1e-10; int dcmp(double x) { if(fabs(x)<eps) return 0; else return x<0?-1:1; } Point operator + (Point p,Vector v) { return Point(p.x+v.x,p.y+v.y); } Vector operator - (Point A,Point B) { return Vector(A.x-B.x,A.y-B.y); } Vector operator * (Vector V,double t) { return Vector(V.x*t,V.y*t); } Vector operator / (Vector V,double t) { return Vector(V.x/t,V.y/t); } double Dot(Vector A,Vector B) { return A.x*B.x+A.y*B.y; } double Cross(Vector A,Vector B) { return A.x*B.y-A.y*B.x; } double Len(Vector V) { return sqrt(Dot(V,V)); } Vector Normal(Vector V) { double L=Len(V); return Vector(-V.y/L,V.x/L); } double angle(Vector v) { return atan2(v.y,v.x); } struct Line { Point p; Vector v; double ang; Line(Point p=Point(),Vector v=Vector()):p(p),v(v) { ang=angle(v); } bool operator < (const Line& rhs) const { return ang<rhs.ang; } }; bool OnLeft(Line L,Point P) { return Cross(L.v,P-L.p)>0; } Point GetLineInterSection(Line L1,Line L2) { Vector u=L2.p-L1.p; double t=Cross(u,L2.v)/Cross(L1.v,L2.v); return L1.p+L1.v*t; } int GetHalfPlaneInterSection(Line* L,int n,Point* Poly) { Point* p=new Point[n]; Line* q=new Line[n]; int first,last; q[first=last=0]=L[0]; for(int i=1;i<n;i++) { while(last>first&&!OnLeft(L[i],p[last-1])) last--; while(last>first&&!OnLeft(L[i],p[first])) first++; q[++last]=L[i]; if(dcmp(Cross(q[last].v,q[last-1].v))==0) { --last; if(OnLeft(q[last],L[i].p)) q[last]=L[i]; } if(first<last) p[last-1]=GetLineInterSection(q[last],q[last-1]); } while(first<last&&!OnLeft(q[first],p[last-1])) last--; if(last-first<=1) return 0; p[last]=GetLineInterSection(q[last],q[first]); int m=0; for(int i=first;i<=last;i++) Poly[m++]=p[i]; return m; } Point ReadPoint() { double x,y; scanf("%lf %lf",&x,&y); return Point(x,y); } int n; Point P[maxn]; Point Poly[maxn]; Line L[maxn]; Line LL[maxn]; const double EPS=1e-7; int main() { while(scanf("%d",&n)==1&&n) { for(int i=0;i<n;i++) P[i]=ReadPoint(); for(int i=0;i<n;i++) L[i]=Line(P[i],P[(i+1)%n]-P[i]); double l=0; double r=3e8; while(r-l>EPS) { double m=l+(r-l)/2; for(int i=0;i<n;i++) { LL[i]=L[i]; LL[i].p=LL[i].p+Normal(LL[i].v)*m; } if(!GetHalfPlaneInterSection(LL,n,Poly)) r=m; else l=m; } printf("%.6lf\n",l); } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-650122.html

    最新回复(0)