CF696F …Dary! 题解

CF696F ...Dary!

题意

• 给定一个 $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)$。

我的计算几何板子比较丑，所以被卡常了，稍微卡一下就过去了。

代码

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;
}