简单几何(半平面交+二分) LA 3890 Most Distant Point from the Sea

时间:2021-08-09 13:27:32

题目传送门

题意:凸多边形的小岛在海里,问岛上的点到海最远的距离。

分析:训练指南P279,二分答案,然后整个多边形往内部收缩,如果半平面交非空,那么这些点构成半平面,存在满足的点。

/************************************************
* Author :Running_Time
* Created Time :2015/11/10 星期二 14:16:17
* File Name :LA_3890.cpp
************************************************/ #include <bits/stdc++.h>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
int dcmp(double x) { //三态函数,减少精度问题
if (fabs (x) < EPS) return 0;
else return x < 0 ? -1 : 1;
}
struct Point { //点的定义
double x, y;
Point () {}
Point (double x, double y) : x (x), y (y) {}
Point operator + (const Point &r) const { //向量加法
return Point (x + r.x, y + r.y);
}
Point operator - (const Point &r) const { //向量减法
return Point (x - r.x, y - r.y);
}
Point operator * (double p) const { //向量乘以标量
return Point (x * p, y * p);
}
Point operator / (double p) const { //向量除以标量
return Point (x / p, y / p);
}
bool operator < (const Point &r) const { //点的坐标排序
return x < r.x || (x == r.x && y < r.y);
}
bool operator == (const Point &r) const { //判断同一个点
return dcmp (x - r.x) == 0 && dcmp (y - r.y) == 0;
}
};
typedef Point Vector; //向量的定义
Point read_point(void) { //点的读入
double x, y; scanf ("%lf%lf", &x, &y);
return Point (x, y);
}
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));
}
double polar_angle(Vector A) { //向量极角
return atan2 (A.y, A.x);
}
Vector nomal(Vector A) { //向量的单位法向量
double len = length (A);
return Vector (-A.y / len, A.x / len);
}
struct Line {
Point p;
Vector v;
double ang;
Line () {}
Line (const Point &p, const Vector &v) : p (p), v (v) {
ang = polar_angle (v);
}
bool operator < (const Line &r) const {
return ang < r.ang;
}
Point point(double a) {
return p + v * a;
}
}; bool point_on_left(Point p, Line L) {
return cross (L.v, p - L.p) > 0;
}
Point line_line_inter(Point p, Vector V, Point q, Vector W) { //两直线交点,参数方程
Vector U = p - q;
double t = cross (W, U) / cross (V, W);
return p + V * t;
} vector<Point> half_plane_inter(vector<Line> L) {
sort (L.begin (), L.end ());
int first, last, n = L.size ();
Point *p = new Point[n];
Line *q = new Line[n];
q[first=last=0] = L[0];
for (int i=1; i<n; ++i) {
while (first < last && !point_on_left (p[last-1], L[i])) last--;
while (first < last && !point_on_left (p[first], L[i])) first++;
q[++last] = L[i];
if (dcmp (cross (q[last].v, q[last-1].v)) == 0) {
last--;
if (point_on_left (L[i].p, q[last])) q[last] = L[i];
}
if (first < last) p[last-1] = line_line_inter (q[last-1].p, q[last-1].v, q[last].p, q[last].v);
}
while (first < last && !point_on_left (p[last-1], q[first])) last--;
vector<Point> ps;
if (last - first <= 1) return ps;
p[last] = line_line_inter (q[last].p, q[last].v, q[first].p, q[first].v);
for (int i=first; i<=last; ++i) ps.push_back (p[i]);
return ps;
} Point ps[110];
Vector V[110], V2[110]; int main(void) {
int n;
while (scanf ("%d", &n) == 1) {
if (!n) break;
for (int i=0; i<n; ++i) ps[i] = read_point ();
for (int i=0; i<n; ++i) {
V[i] = ps[(i+1)%n] - ps[i];
V2[i] = nomal (V[i]);
}
double l = 0, r = 20000;
while (r - l > EPS) {
double mid = l + (r - l) / 2;
vector<Line> L;
for (int i=0; i<n; ++i) {
L.push_back (Line (ps[i] + V2[i] * mid, V[i]));
}
vector<Point> qs = half_plane_inter (L);
int sz = qs.size ();
if (sz == 0) r = mid;
else l = mid;
}
printf ("%.6f\n", l);
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}