BZOJ4140: 共点圆加强版 二进制分组+三分+点积

题目大意：

共点圆的强制在线版。

算法讨论：

对于点$(x,y)$，若在以点$(x_0,y_0)$为圆心的圆中，当且仅当$(x-x_0)^2+(y-y_0)^2\leq{x_0^2+y_0^2}$。

整理得：$2x_0x+2y0y\geq{x^2+y^2}$。

我们可以将左侧看成向量$(2x_0,2y_0)$与向量$(x,y)$的点积，那么我们只要求出向量$(x,y)$与所有向量$(2x_0,2y_0)$的点积的最小值，再判断与$x^2+y^2$的大小关系即可。

点积的最值必定出现在凸壳上且在凸壳上是单峰函数，要求最小值的话，若$y>0$则在下凸壳上三分，否则在上凸壳上三分。

最后再证明这些结论。

我们可以利用高级数据结构动态维护上下凸壳，但是这样比较繁琐；由于强制在线的话也不能使用按时间分治。

这时我们可以使用二进制分组，假如现在我们已经插入了$n$个点，我们维护$n$的二进制表示中的$1$的个数个凸包，例如$n=27$，则维护$4$个凸包，分别是$[1,16],[17,24],[25,26],[27,27]$，长度分别为$16,8,2,1$。

询问的话，分别在这些凸包上三分即可，时间复杂度$O(\log ^2n)$，常数很小。

假如现在要再插入一个点，我们从后往前找$1,2,4,...$直到不符合这个规律，然后将这些凸包中的点取出再加上新插入的点暴力重构成一个新的凸包，例如$n=27$要插入第$28$个点，我们找到$1,2$，然后将区间$[25,28]$重构成一个新的凸包，现在的长度分别为$16,8,4$。

我们用$O(n\log n)$的复杂度求凸包，那么其复杂度是多少呢？

我们不难发现插入第$n$个点时要重构大小为$n$的二进制最低位的凸包，对于第$i$位，每插入$2^i$个点贡献一次复杂度，其复杂度为$i2^i$，于是第$i$位每次贡献的复杂度就为$i$，于是所有位每次贡献的复杂度就为$O(1+2+...+\log n)=O(\log ^2n)$。

于是这题就在$O(n\log ^2n)$的时间内解决了。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define N 500010
typedef double db;
static const db eps = 1e-8;
int n;
int dcmp(const db &x) {
	if (fabs(x) < eps)
		return 0;
	return x < 0 ? -1 : 1;
}
struct Point {
	db x, y;
	Point() {}
	Point(db _x, db _y) : x(_x), y(_y) {}
	friend bool operator < (const Point &a, const Point &b) {
		if (dcmp(a.x - b.x) != 0)
			return a.x < b.x;
		return a.y < b.y;
	}
	friend bool operator == (const Point &a, const Point &b) {
		return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
	}
}P[N], Q[N], stack[N];

int l[32], r[32], c[32], num;
vector<Point> up[32], down[32];
bool goup(Point a, Point b, Point c) {
	return (c.y - b.y) * (b.x - a.x) >= (b.y - a.y) * (c.x - b.x);
}
bool godown(Point a, Point b, Point c) {
	return (c.y - b.y) * (b.x - a.x) <= (b.y - a.y) * (c.x - b.x);
}
void rebuild(int l, int r, int id) {
	up[id].clear();
	down[id].clear();
	static int i, j, m, top;
	sort(P + l, P + r + 1);
	top = 0;
	for (i = l; i <= r; ++i) {
		while (top >= 2 && goup(stack[top - 1], stack[top], P[i]))
			--top;
		stack[++top] = P[i];
	}
	for (i = 1; i <= top; ++i)
		up[id].push_back(stack[i]);
	top = 0;
	for (i = l; i <= r; ++i) {
		while (top >= 2 && godown(stack[top - 1], stack[top], P[i]))
			--top;
		stack[++top] = P[i];
	}
	for (i = 1; i <= top; ++i)
		down[id].push_back(stack[i]);
}
db askup(int id, db x, db y) {
	static int L, R, ll, rr;
	static db ans, ansl, ansr;
	ans = 1e10;
	L = 0, R = up[id].size() - 1;
	while (1) {
		if (R - L <= 3) {
			for (int i = L; i <= R; ++i)
				ans = min(ans, x * up[id][i].x + y * up[id][i].y);
			break;
		}
		ll = L + (R - L) / 3;
		rr = R - (R - L) / 3;
		ansl = x * up[id][ll].x + y * up[id][ll].y;
		ansr = x * up[id][rr].x + y * up[id][rr].y;
		if (ansl < ansr)
			R = rr;
		else
			L = ll;
	}
	return ans;
}
db askdown(int id, db x, db y) {
	static int L, R, ll, rr;
	static db ans, ansl, ansr;
	ans = 1e10;
	L = 0, R = down[id].size() - 1;
	while (1) {
		if (R - L <= 3) {
			for (int i = L; i <= R; ++i)
				ans = min(ans, x * down[id][i].x + y * down[id][i].y);
			break;
		}
		ll = L + (R - L) / 3;
		rr = R - (R - L) / 3;
		ansl = x * down[id][ll].x + y * down[id][ll].y;
		ansr = x * down[id][rr].x + y * down[id][rr].y;
		if (ansl < ansr)
			R = rr;
		else
			L = ll;
	}
	return ans;
}

int cnt;
int main() {
#ifndef ONLINE_JUDGE
	freopen("tt.in", "r", stdin);
#endif
	scanf("%d", &n);
	int i, j, lastans = 0, qte, size;
	db x, y;
	while (n--) {
		scanf("%d%lf%lf", &qte, &x, &y);
		x += lastans;
		y += lastans;
		if (qte == 0) {
			P[++cnt] = Point(x * 2, y * 2);
			for (size = 1, i = num; i > 0 && size == c[i]; --i, size <<= 1);
			num = i + 1;
			l[num] = r[i] + 1;
			r[num] = cnt;
			c[num] = r[num] - l[num] + 1;
			rebuild(l[num], r[num], num);
		}
		else {
			if (num == 0)
				puts("No");
			else {
				db ans = 1e10;
				for (i = 1; i <= num; ++i) {
					if (y > 0)
						ans = min(ans, askdown(i, x, y));
					else
						ans = min(ans, askup(i, x, y));
				}
				if (dcmp(ans - x * x - y * y) >= 0) {
					++lastans;
					puts("Yes");
				}
				else
					puts("No");
			}
		}
	}
	return 0;
}

有时间再来更新求点积最值的证明。

我是卧底不要打脸。