UVA1396 Most Distant Point from the Sea（AM - ICPC - Tokyo - 2007）（计算几何，半平面交 + 二分答案）

整理的算法模板合集： ACM模板

---

题目传送门

见《训练指南》P279
很明显就是一个二分答案，它问的是最远的点，直接枚举因为这里都是double类型的数所以有无限个点，我们可以直接二分。
判定依据就是是否有离海距离不小于mid的点出现，对于每条边来说，这些点形成一个半平面。

我们根据二分的mid将整个图进行收缩放大，看能否有一个半平面存在，这个半平面里的所有的点都是距离所有海边的距离大于等于mid的点，极限条件就是整个图的好多个边（有向直线）缩小mid之后的半平面交到了一个点，这个点就是我们要找到点，答案就是mid，再大一点，就不再会形成半平面交，交集为空，mid大了，令r = mid。

#include<bits/stdc++.h>
using namespace std;

const int N = 507, M = 507, INF = 0x3f3f3f3f;
const double DINF = 12345678910, eps = 1e-10, PI = acos(-1);
struct Point{
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){ }//构造函数
};

//!注意区分点和向量
typedef Point Vector;
//!向量 + 向量 = 向量，点 + 向量 = 向量
Vector operator + (Vector A, Vector B){return Vector(A.x + B.x, A.y + B.y);}
//!点 - 点 = 向量(向量BC = C - B)
Vector operator - (Point A, Point B){return Vector(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);}

//!点/向量的比较函数
bool operator < (const Point& a, Point& b) {return a.x < b.x || (a.x == b.x && a.y < b. y);}
//!三态函数dcmp用于判断相等，减少精度问题

int dcmp(double x){
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
//重载等于运算符
bool operator == (const Point& a, const Point& b){return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);}

//!求极角
//单位弧度rad
double Polar_angle(Vector A){return atan2(A.y, A.x);}

double Dot(Vector A, Vector B){return A.x * B.x + A.y * B.y;}
double Length(Vector A){return sqrt(Dot(A, A));}

//计算凸包，输入点数组p，个数为p输出点数组ch，函数返回凸包顶点个数。
//输入不能有重复的点，函数执行完后的输入点的顺序将被破坏（因为要排序，可以加一个数组存原来的id）
//如果不希望在凸包边上有输入点，把两个<=改成<即可
inline double D_to_R(double D)//角度转弧度
{ return PI/180*D; }
double Cross(Vector A, Vector B){return A.x * B.y - B.x * A.y;}
Vector Rotate(Vector A, double rad){
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}

Point Get_line_intersection(Point P,Vector v,Point Q,Vector w)
{
	Vector u = P - Q;
	double t = Cross(w, u) / Cross(v, w);
	return P + v * t;
}
double convex_polygon_area(Point* p, int n)
{
    double area = 0;
    for(int i = 1; i <= n - 2; ++ i)
        area += Cross(p[i] - p[0], p[i + 1] - p[0]);
    return area / 2;
}
//凸包
int ConvexHull(Point* p, int n, Point* ch)
{
    sort(p, p + n);
    int m = 0;
    for(int i = 0; i < n; ++ i){//下凸包
        //如果叉积<=0说明新边斜率小说明已经不是凸包边了，赶紧踢走
        while(m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0)m -- ;
        ch[m ++ ] = p[i];
    }
    int k = m;
    for(int i = n - 2; i >= 0; -- i){//上凸包
        while(m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0)m -- ;
        ch[m ++ ] = p[i];
    }
    if(n > 1) m -- ;
    return m;
}

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

//有向直线。它的左边就是对应的半平面
struct Line
{
    Point P;//直线上任意一点
    Vector v;//方向向量。左边就是对应的半平面
    double deg;//极角
    Line(){}
    Line(Point P, Vector v):P(P), v(v){deg = atan2(v.y, v.x);}
    bool operator < (const Line& L)const {//排序时使用的比较运算符
        return deg < L.deg;
    }
};



//半平面交
//半平面交一般是一个凸多边形，但是有时候会是一个*多边形
//甚至会是一个直线、线段、点，但是结果一定是凸的

//点p在有向直线L的左边（线上的不算）（叉积大于0a在b的左侧，小于0在右侧[sin夹角]）
bool on_left(Line L, Point P){return Cross(L.v, P - L.P) > 0;}
//两个有向直线的交点/假定交点唯一存在
Point get_intersection(Line a, 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;
}
//半平面交的主过程
int half_plane_intersection(Line* L, int n, Point* poly)
{
    sort(L, L + n);//按照极角排序

    int first, last;//双端队列
    Point *p = new Point[n];//p[i]为q[i]和q[i + 1]的交点
    Line *q = new Line[n];//手写的Line类型的双端队列（数组）
    q[first = last = 0] = L[0];//双端队列初始化的时候只有一个半平面L[0]
    for(int i = 1; i < n; ++ i){
        while(first < last && !on_left(L[i], p[last - 1]))last -- ;
        while(first < last && !on_left(L[i], p[first]))first ++ ;
        q[++ last] = L[i];//新的点是一定要放进去的
        if(fabs(Cross(q[last].v, q[last - 1].v)) < eps){
        //相邻的两个向量平行且同向，取内侧的那一个
            last -- ;//如果新的向量上的一个点在老的向量的左侧就取新的
            if(on_left(q[last], L[i].P))q[last] = L[i];
        }
        if(first < last)p[last - 1] = get_intersection(q[last - 1], q[last]);
    }
    while(first < last && !on_left(q[first], p[last - 1]))last -- ;
    //删除无用的平面

    if(last - first <= 1)return 0;//空集
    p[last] = get_intersection(q[last], q[first]);//计算首尾两个半平面交（环状）
    //从手写deque中复制答案到输出数组中
    int m = 0;
    for(int i = first ; i <= last; ++ i)poly[m ++ ] = p[i];
    return m;
}
Point p[N], poly[N];
Line L[N];
Vector v[M], v2[M];
int n;

int main()
{
    while(scanf("%d", &n) != EOF && n)
    {
        int m, x, y;
        for(int i = 0; i < n; ++i){
            scanf("%d%d", &x, &y);
            p[i] = Point(x, y);
        }
        for(int i = 0; i < n; ++ i){
            v[i] = p[(i + 1) % n] - p[i];
            v2[i] = Normal(v[i]);//单位法向量
        }
        double l = 0, r = 20000;
        while(r - l > eps){
            double mid = l + (r - l) / 2;
            for(int i = 0; i < n; ++ i)
                L[i] = Line(p[i] + v2[i] * mid, v[i]);
           //收缩/放大整个凸多边形
           //点+单位向量*长度=平移后的点
           m = half_plane_intersection(L, n, poly);
           if(!m)r = mid;
           else l = mid;
        }
        printf("%.6f\n", l);
    }
    return 0;
}