LA 3890 (半平面交) Most Distant Point from the Sea

时间：2021-11-14 10:43:23

题意：

给出一个凸n边形，求多边形内部一点使得该点到边的最小距离最大。

分析：

最小值最大可以用二分。

多边形每条边的左边是一个半平面，将这n个半平面向左移动距离x，则将这个凸多边形缩小了。如果这n个半平面交非空，则存在这样距离为x的点，反之则不存在。

半平面交的代码还没有完全理解。

和凸包类似，先对这些半平面进行极角排序。每次新加入的平面可能让队尾的平面变得“无用”，从而需要删除。由于极角序是环形的，所以也可能让队首元素变得“无用”。所以用双端队列来维护。

 //#define LOCAL

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 using namespace std;

 const double eps = 1e-;

 struct Point

 {

     double x, y;

     Point(double x=, double y=):x(x), y(y){}

 };

 typedef Point Vector;

 Point operator + (Point A, Point B) { return Point(A.x+B.x, A.y+B.y); }

 Point operator - (Point A, Point B) { return Point(A.x-B.x, A.y-B.y); }

 Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }

 Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }

 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 Length(Vector A) { return sqrt(Dot(A, A)); }

 Vector Normal(Vector A) { double l = Length(A); return Vector(-A.y/l, A.x/l); }

 double PolygonArea(const vector<Point>& p)

 {

     double ans = 0.0;

     int n = p.size();

     for(int i = ; i < n-; ++i)

         ans += Cross(p[i]-p[], p[i+]-p[]);

     return ans/;

 }

 struct Line

 {

     Point p;

     Vector v;

     double ang;

     Line() {}

     Line(Point p, Vector v):p(p), v(v) { ang = atan2(v.y, v.x); }

     bool operator < (const Line& L) const

     {

         return ang < L.ang;

     }

 };

 bool OnLeft(const Line& L, const Point& p)

 { return Cross(L.v, p-L.p) > ; }

 Point GetLineIntersection(const Line& a, const 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;

 }

 vector<Point> HalfplaneIntersection(vector<Line> L)

 {

     int n = L.size();

     sort(L.begin(), L.end());

     int first, last;

     vector<Point> p(n);

     vector<Line> q(n);

     vector<Point> ans;

     q[first=last=] = L[];

     for(int i = ; i < n; ++i)

     {

         while(first < last && !OnLeft(L[i], p[last-])) last--;

         while(first < last && !OnLeft(L[i], p[first])) first++;

         q[++last] = L[i];

         if(fabs(Cross(q[last].v, q[last-].v)) < eps)    //Èç¹ûÁ½Ö±ÏßƽÐУ¬È¡ÄÚ²àµÄÄǸö

         {

             last--;

             if(OnLeft(q[last], L[i].p)) q[last] = L[i];

         }

         if(first < last) p[last-] = GetLineIntersection(q[last-], q[last]);

     }

     while(first < last && !OnLeft(q[first], p[last-])) last--;

     if(last - first <= )    return ans;

     p[last] = GetLineIntersection(q[last], q[first]);

     for(int i = first; i <= last; ++i)    ans.push_back(p[i]);

     return ans;

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("3890in.txt", "r", stdin);

     #endif

     int n;

     while(scanf("%d", &n) ==  && n)

     {

         vector<Point> p, v, normal;

         int m, x, y;

         for(int i = ; i < n; ++i) { scanf("%d%d", &x, &y); p.push_back(Point(x, y)); }

         if(PolygonArea(p) < ) reverse(p.begin(), p.end());

         for(int i = ; i < n; ++i)

         {

             v.push_back(p[(i+)%n] - p[i]);

             normal.push_back(Normal(v[i]));

         }

         double left = , right = ;

         while(right - left > 5e-)

         {

             vector<Line> L;

             double mid = (right + left) / ;

             for(int i = ; i < n; ++i) L.push_back(Line(p[i] + normal[i]*mid, v[i]));

             vector<Point> Poly = HalfplaneIntersection(L);

             if(Poly.empty())    right = mid;

             else left = mid;

         }

         printf("%.6lf\n", left);

     }

     return ;

 }

代码君

相关文章