题解 CF696F 【...Dary!】
xht
2020-03-10 22:04:54
> [CF696F ...Dary!](https://codeforces.com/contest/696/problem/F)
## 题意
- 给定一个 $n$ 个点的严格凸多边形。
- 你要最小化 $r$，使得可以在这个多边形内或多边形上找到两个点，以它们为圆心以 $r$ 为半径作两个圆，满足多边形的每条边所在的直线与至少一个圆有交点。
- $n \le 300$，答案精度误差 $\le 10^{-6}$。
## 题解
首先二分答案，设此时二分的值为 $r$。
对于一个直线集，如何判断多边形内是否存在一个点，满足以它为圆心以 $r$ 为半径作的圆与直线集中的直线有交点呢？
对于每条直线，这个点一定在与这条直线相距 $r$ 的两条平行线内，也就是两个半平面的交。而多边形也可以看成若干个半平面的交，于是问题变成这若干个半平面是否有交。
那么，如果我们能够把边分成两类，第一类和第二类分别有解，则说明此时的 $r$ 满足条件。
注意到，最终的最优解一定是两个多边形的顶点分隔成的两类，因为如果不是，显然可以通过调整达到更优解。
于是我们可以 $\mathcal O(n)$ two pointers，$\mathcal O(n \log n)$ 半平面交判定。
总时间复杂度 $\mathcal O(n^2 \log n \log w)$。
我的计算几何板子比较丑，所以被卡常了，稍微卡一下就过去了。
## 代码
```cpp
const double eps = 1e-10, PI = acos(-1);
struct P {
double x, y;
inline P() {}
inline P(double x, double y) : x(x), y(y) {}
inline P &operator += (P o) { return x += o.x, y += o.y, *this; }
inline P &operator -= (P o) { return x -= o.x, y -= o.y, *this; }
inline P &operator *= (double o) { return x *= o, y *= o, *this; }
inline P &operator /= (double o) { return x /= o, y /= o, *this; }
inline friend P operator + (P a, P b) { return a += b; }
inline friend P operator - (P a, P b) { return a -= b; }
inline friend P operator * (P a, double b) { return a *= b; }
inline friend P operator / (P a, double b) { return a /= b; }
inline friend bool operator < (P a, P b) { return fabs(a.x - b.x) < eps ? a.y < b.y : a.x < b.x; }
inline friend bool operator == (P a, P b) { return !(a < b) && !(b < a); }
inline friend double operator * (P a, P b) { return a.x * b.x + a.y * b.y; }
inline friend double operator % (P a, P b) { return a.x * b.y - a.y * b.x; }
inline friend double operator ^ (P a, P b) { return a * b / a.l() / b.l(); }
inline double a() { return atan2(y, x); }
inline double l() { return sqrt(*this * *this); }
inline void r(double o) { double s = sin(o), c = cos(o), X = x * c - y * s, Y = x * s + y * c; x = X, y = Y; }
};
struct L {
P a, b;
double c;
inline L() {}
inline L(P a, P b) : a(a), b(b) { c = b.a(); }
inline friend P operator * (L a, L b) { return a.a + a.b * (b.b % (a.a - b.a) / (a.b % b.b)); }
inline friend double operator / (L a, P b) { return fabs(a.b % (b - a.a)) / a.b.l(); }
inline friend bool operator < (L a, L b) { return fabs(a.c - b.c) < eps ? (b.a - a.a) % a.b < 0 : a.c < b.c; }
};
inline deque<P> half_plane(vector<L> l) {
sort(l.begin(), l.end());
deque<P> r;
deque<L> q;
for (L o : l) {
while (r.size() && (r.back() - o.a) % o.b > 0)
q.pop_back(), r.pop_back();
while (r.size() && (r.front() - o.a) % o.b > 0)
q.pop_front(), r.pop_front();
if (q.size() && fabs(o.b % q.back().b) < eps) {
if (fabs(o.b.a() - q.back().b.a()) > eps)
return r.clear(), r;
q.pop_back();
if (r.size()) r.pop_back();
}
if (q.size()) r.pb(q.back() * o);
q.pb(o);
}
while (r.size() && (r.back() - q.front().a) % q.front().b > 0)
q.pop_back(), r.pop_back();
if (q.size() < 3u) r.clear();
else r.pb(q.front() * q.back());
return r;
}
int n;
vector<L> l, q;
P p1, p2, ans1, ans2;
inline bool pd(int i, int j, double r, P& t) {
vector<L> s = q;
for (int k = i; k <= j; k++) {
L o = l[k];
P p = o.b;
p.r(PI / 2);
p *= r / p.l();
o.a += p, o.b *= -1, o.c = o.b.a();
s.pb(o);
}
deque<P> p = half_plane(s);
if (!p.size()) return 0;
return t = p.back(), 1;
}
inline bool pd(double r) {
for (int i = 0, j = 0; i < n; i++) {
while (j < i + n - 2 && pd(i, j, r, p1)) ++j;
if (pd(j, i + n - 1, r, p2)) return 1;
}
return 0;
}
int main() {
rd(n);
vector<P> p;
for (int i = 1, x, y; i <= n; i++) rd(x), rd(y), p.pb(P(x, y));
p.pb(p[0]);
for (int i = 0; i < n; i++) l.pb(L(p[i], p[i+1] - p[i]));
p.pop_back(), q = l;
for (int i = 0; i < n; i++) l.pb(l[i]);
double l = 0, r = 1e5;
while (r - l > eps) {
double mid = (l + r) / 2;
if (pd(mid)) r = mid, ans1 = p1, ans2 = p2;
else l = mid;
}
printf("%.10f\n", r);
printf("%.10f %.10f\n", ans1.x, ans1.y);
printf("%.10f %.10f\n", ans2.x, ans2.y);
return 0;
}
```