UVa 1396 Most Distant Point from the Sea

问题重述

给定一个凸多边形（岛屿的地图），我们需要找到多边形内部一点，使得该点到多边形边界（即大海）的最短距离最大。 换句话说，就是要求这个凸多边形内最大内切圆的半径。

问题分析

这个问题可以转化为一个最优化问题：我们希望找到一个点PPP，使得它到所有边（直线）的距离的最小值最大。 形式化地，就是求：

max⁡P∈Polygonmin⁡idistance(P,Edgei) \max_{P \in \texttt{Polygon}} \min_{i} \texttt{distance}(P, \text{Edge}_i)P∈Polygonmax​imin​distance(P,Edgei​)

其中distance(P,Edgei)\texttt{distance}(P, \texttt{Edge}_i)distance(P,Edgei​)是点PPP到第iii条边所在直线的有向距离。

直接求解这个最值问题比较困难。 一个关键的观察是：如果我们能猜到这个最大距离的值ddd，那么我们可以验证它是否可行。

解题思路： 二分答案 + 半平面交

1. 二分答案

我们最终要求的答案是一个距离rrr。 显然rrr的范围是[0,R][0, R][0,R]，其中RRR是多边形的一个特征长度（例如最长边的一半）。 由于坐标范围是[0,10000][0, 10000][0,10000]，我们可以保守地将二分上界定为200002000020000。

我们可以对rrr进行二分搜索。 对于每次猜测的中间值midmidmid， 我们检查是否存在一个点PPP，使得它到每条边的距离都至少为midmidmid。 如果可以，说明midmidmid是可行的，我们就可以尝试更大的值（收缩左边界）； 如果不可以，说明midmidmid太大了，我们需要尝试更小的值（收缩右边界）。

2. 如何验证距离ddd是否可行？

对于一个给定的距离ddd， “存在一个点PPP到所有边的距离≥d\ge d≥d” 这个条件， 等价于将多边形的每条边向内（朝向多边形中心）平移距离ddd后， 这些新的半平面（平移后直线的左侧区域）的交集非空。

• 为什么是向内平移？因为多边形是逆时针给出的， 每条边的“左侧”就是多边形的内部。 要保证点PPP到该边的距离至少为ddd，PPP必须位于这条边向内平移ddd后形成的新直线的左侧。
• 平移操作： 对于一条边AB→\overrightarrow{AB}AB， 其方向向量为v⃗=B−A\vec{v} = B - Av=B−A。 一个垂直于v⃗\vec{v}v且指向多边形内部的法向量n⃗\vec{n}n可以通过n⃗=(−vy,vx)\vec{n} = (-v_y, v_x)n=(−vy​,vx​)获得（因为逆时针顺序）。 将n⃗\vec{n}n单位化后， 边ABABAB对应的新直线就是过点A+n⃗∗dA + \vec{n} * dA+n∗d且方向为v⃗\vec{v}v的直线。
• 可行性判断： 对平移后所有边对应的半平面（新直线的左侧区域）求交集。 如果交集（一个凸多边形区域）非空， 则ddd可行； 如果交集为空， 则ddd不可行。

3. 算法步骤总结

1. 读入凸多边形的顶点。
2. 初始化二分边界left = 0,right = 20000。
3. Whileright - left > EPS（例如10−810^{-8}10−8）：
   1. mid = (left + right) / 2。
   2. 根据mid构造向内缩进的所有半平面。
   3. 调用半平面交算法，计算这些半平面的交集。
   4. If交集非空： 说明mid可行，left = mid。
   5. Else： 说明mid太大，right = mid。
4. 输出left（即满足条件的最大距离rrr）。

时间复杂度： 半平面交的复杂度为O(nlog⁡n)O(n \log n)O(nlogn)， 其中nnn是顶点数（n≤100n \le 100n≤100）。 二分次数约log⁡2(20000EPS)≈50\log_2(\frac{20000}{EPS}) \approx 50log2​(EPS20000​)≈50次。 总体计算量很小。

关键点与细节

• 凸性保证： 题目保证输入是凸多边形，这简化了问题。 对于凸多边形， 向内缩进后形成的半平面交仍然是一个凸多边形（或空集）， 并且半平面交算法更稳定。
• 精度控制： 题目要求误差不超过10−510^{-5}10−5。 在二分和几何运算中使用10−810^{-8}10−8的EPS可以保证精度。
• 半平面交算法： 这是本体的核心。 算法步骤通常为：
  1. 将所有半平面（直线）按极角排序。
  2. 使用双端队列维护可能构成最终交集的半平面。
  3. 不断检查队首/队尾的半平面是否冗余（即其与新加入半平面的交点不在当前半平面内）。
  4. 最后检查队首和队尾的半平面是否矛盾。
  5. 计算队列中相邻半平面的交点， 得到最终交集多边形的顶点。

参考代码

// Most Distant Point from the Sea// UVa ID: 1396// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleEPS=1e-8;// 精度控制constdoubleINF=1e10;// 无穷大// 点与向量structPoint{doublex,y;Point(doublex=0,doubley=0):x(x),y(y){}Pointoperator+(constPoint&b)const{returnPoint(x+b.x,y+b.y);}Pointoperator-(constPoint&b)const{returnPoint(x-b.x,y-b.y);}Pointoperator*(doublek)const{returnPoint(x*k,y*k);}Pointoperator/(doublek)const{returnPoint(x/k,y/k);}doubledot(constPoint&b)const{returnx*b.x+y*b.y;}doublecross(constPoint&b)const{returnx*b.y-y*b.x;}doublelength()const{returnsqrt(x*x+y*y);}Pointnormal()const{returnPoint(-y,x);}// 逆时针旋转90度（法向量）};// 直线/半平面：点p，方向向量v，左侧为半平面structLine{Point p,v;doubleangle;Line(){}Line(Point p,Point v):p(p),v(v){angle=atan2(v.y,v.x);}booloperator<(constLine&b)const{returnangle<b.angle;}Pointintersect(constLine&b)const{Point u=p-b.p;doublet=b.v.cross(u)/v.cross(b.v);returnp+v*t;}boolonLeft(Point pt)const{returnv.cross(pt-p)>EPS;}// 点在半平面左侧（严格）};// 半平面交（返回多边形点集，若为空表示无解）vector<Point>halfplaneIntersection(vector<Line>lines){intn=lines.size();sort(lines.begin(),lines.end());intfirst=0,last=0;vector<Point>p(n);vector<Line>q(n);q[0]=lines[0];for(inti=1;i<n;i++){while(first<last&&!lines[i].onLeft(p[last-1]))last--;while(first<last&&!lines[i].onLeft(p[first]))first++;q[++last]=lines[i];if(fabs(q[last].v.cross(q[last-1].v))<EPS){// 平行last--;if(q[last].onLeft(lines[i].p))q[last]=lines[i];}if(first<last)p[last-1]=q[last-1].intersect(q[last]);}while(first<last&&!q[first].onLeft(p[last-1]))last--;if(last-first<=1)returnvector<Point>();// 空集p[last]=q[last].intersect(q[first]);vector<Point>res;for(inti=first;i<=last;i++)res.push_back(p[i]);returnres;}intmain(){intn;while(cin>>n&&n){vector<Point>poly(n);for(inti=0;i<n;i++)cin>>poly[i].x>>poly[i].y;doubleleft=0,right=20000;// 最大距离不超过坐标范围while(right-left>EPS){doublemid=(left+right)/2;vector<Line>lines;// 构造向内缩进mid的半平面for(inti=0;i<n;i++){Point a=poly[i],b=poly[(i+1)%n];Point dir=b-a;Point normal=Point(-dir.y,dir.x);// 法向量（指向多边形内部，因为顶点逆时针）normal=normal/normal.length();// 单位化lines.push_back(Line(a+normal*mid,dir));// 边向内平移mid}vector<Point>res=halfplaneIntersection(lines);if(res.empty())right=mid;// 无解，距离太大elseleft=mid;// 有解，可以尝试更大距离}printf("%.6lf\n",left);// 输出左端点（满足条件）}return0;}

总结

本题是一个经典的几何最优化问题， 通过二分答案将最优化问题转化为判定性问题， 再利用半平面交这一强大的几何工具进行判定。 题目融合了二分搜索、 计算几何（向量运算、 直线表示、 半平面交）等多个知识点， 是一道非常好的综合练习题。 掌握半平面交算法是解决此类问题的关键。