CF549E Sasha Circle 题解

CF549E Sasha Circle

题意

• $n+m$ 个整点。
• 询问是否存在一个圆将前 $n$ 个点和后 $m$ 个点严格分开。
• $n,|x|,|y| \le 10^4$。

题解

设 $A$ 为前 $n$ 个点的集合，$B$ 为后 $m$ 个点的集合，不妨设圆内为 $A$。

首先可以发现第一个性质：

题目要求严格分开，实际上相当于找到一个圆，使 $A$ 在圆内或圆上，而 $B$ 都在圆外。

因为如果能找到，那么意味着可以将这样一个圆稍稍放大，从而做到严格分开。

因此，我们还可以将这个圆尽量缩小，使得至少有两个 $A$ 中的点在圆上。

那么就有一个朴素做法：

枚举这两个在圆上的点，那么圆心只能在这两个点的中垂线上，而其他点是否在圆外可以转化为对圆心的限制，如果存在满足所有限制的圆心，则存在一个符合要求的圆。

时间复杂度为 $\mathcal O(n^2(n+m))$。同时，为了方便，我们可以不必算出圆心，而是对圆周角的余切值加以限制，而角的余切值正好等于点积除以叉积，易于计算。

考虑优化，可以发现并不需要对所有 $A$ 中的点对进行一次上述操作。

建立一个三维坐标系，将 $A,B$ 放在 $z=0$ 的平面上。

作一个抛物面 $z = x^2 + y^2$，将 $A,B$ 垂直投影到这个抛物面上得到 $A_0, B_0$。

考虑任意一个不垂直且与抛物面有交的平面 $z = ax + by + c$，与抛物面的解析式联立可以得到 $x^2 + y^2 - ax - by - c = 0$，发现这是一个圆。

因此，我们可以得到一条重要的性质：平面上的圆与不垂直且与抛物面有交的平面一一对应。

那么，问题转化为，能否找到一个不垂直且与抛物面有交的平面，使得 $A_0$ 都在此平面下方或此平面上，$B_0$ 都严格在此平面上方。

此时显然只需要保留 $A_0$ 的上凸壳，又由于 $z = x^2 + y^2$ 是下凸的，所以 $A_0$ 的上凸壳一定是 $A$ 的凸包的一个三角剖分在抛物面上的投影。

那么我们只需要对这个三角剖分中的每一条边进行一次朴素做法即可，因为最终要求的圆在抛物面上的投影一定可以经过一条上凸壳中的棱，而每条棱都对应着三角剖分中的一条边。

由于整点凸包的点数上界为 $\mathcal O(C^{\frac 23})$，其中 $C$ 是值域，因此这个做法的时间复杂度为 $\mathcal O(C^{\frac 23}(n + m))$。

还剩下一个问题，如何在可接受的时间复杂度下求出 $A_0$ 的上凸壳，即 $A$ 的凸包的一个特定的三角剖分？

可以发现，这个上凸壳每一个面在 $z = 0$ 的投影都满足所有顶点共圆且外接圆包含 $A$ 中的所有点。

因此，我们可以一开始随便确定凸包的一条边 $p_1,p_2$，然后找到凸包上的另一个顶点 $p_k$ 使 $p_1,p_2,p_k$ 确定的圆最大。显然此时这个圆一定包含凸包的所有顶点，因此要构造的三角剖分中一定有 $p_1,p_2,p_k$ 这个三角形。然后原问题转化成由 $p_1p_k$ 和 $p_2p_k$ 割开的两个规模更小的子问题，分治递归求解即可，时间复杂度 $\mathcal O(C^{\frac 43})$。

总时间复杂度 $\mathcal O(C^{\frac 43} + C^{\frac 23}(n + m))$。

代码

const ld eps = 1e-10L, PI = acos(-1);

struct P {
	int x, y;
	inline P() {}
	inline P(int x, int 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 friend P operator + (P a, P b) { return a += b; }
	inline friend P operator - (P a, P b) { return a -= b; }
	inline friend bool operator < (P a, P b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
	inline friend int operator * (P a, P b) { return a.x * b.x + a.y * b.y; }
	inline friend int operator % (P a, P b) { return a.x * b.y - a.y * b.x; }
};

const int N = 1e4 + 7;
int n, m, t;
P a[N], b[N], c[N];

inline bool chk(P x, P y) {
	ld l = -1e100L, r = 1e100L;
	for (int i = 1; i <= n; i++) {
		P o = a[i];
		if (!((x - o) % (y - o))) continue;
		ld w = 1.0L * ((x - o) * (y - o)) / ((x - o) % (y - o));
		if ((o - x) % (y - x) < 0) l = max(l, w);
		else r = min(r, w);
	}
	for (int i = 1; i <= m; i++) {
		P o = b[i];
		if (!((x - o) % (y - o))) {
			if (o.x >= min(x.x, y.x) && o.x <= max(x.x, y.x) && o.y >= min(x.y, y.y) && o.y <= max(x.y, y.y)) return 0;
			continue;
		}
		ld w = 1.0L * ((x - o) * (y - o)) / ((x - o) % (y - o));
		if ((o - x) % (y - x) > 0) l = max(l, w);
		else r = min(r, w);
	}
	return l + eps < r;
}

inline bool dfs(int l, int r) {
	if (l + 1 == r) return 0;
	int x;
	ld k = 1e100L;
	for (int i = l + 1; i < r; i++) {
		P o = c[i];
		ld w = 1.0L * ((o - c[l]) * (o - c[r])) / ((o - c[l]) % (o - c[r]));
		if (w < k) x = i, k = w;
	}
	return chk(c[l], c[x]) || chk(c[r], c[x]) || dfs(l, x) || dfs(x, r);
}

inline bool pd() {
	t = 0;
	for (int i = 1; i <= n; i++) {
		while (t > 1 && (c[t] - c[t-1]) % (a[i] - c[t-1]) <= 0) --t;
		c[++t] = a[i];
	}
	int o = t;
	for (int i = n - 1; i; i--) {
		while (t > o && (c[t] - c[t-1]) % (a[i] - c[t-1]) <= 0) --t;
		c[++t] = a[i];
	}
	--t;
	return chk(c[1], c[t]) || dfs(1, t);
}

int main() {
	rd(n), rd(m);
	if (n == 1 || m == 1) return prints("YES"), 0;
	for (int i = 1, x, y; i <= n; i++) rd(x), rd(y), a[i] = P(x, y);
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), b[i] = P(x, y);
	sort(a + 1, a + n + 1), sort(b + 1, b + m + 1);
	prints(pd() || (swap(a, b), swap(n, m), pd()) ? "YES" : "NO");
	return 0;
}