【LG4631】[APIO2018]Circle selection 选圆圈

题面

洛谷

题解

用\(kdt\)乱搞剪枝。

维护每个圆在\(x、y\)轴的坐标范围

相当于维护一个矩形的坐标范围为\([x-r,x+r],[y-r,y+r]\)

可以减小搜索范围

然后再判断一下一个圆是否在当前搜索的矩形内，不在就剪枝

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

	register int data = 0, w = 1;

	register char ch = 0;

	while (!isdigit(ch) && ch != '-') ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

	return w * data;

}

void chkmin(int &x, int y) { if (x > y) x = y; }

void chkmax(int &x, int y) { if (x < y) x = y; }

#define sqr(x) (1ll * (x) * (x))

const int MAX_N = 3e5 + 10;

struct Point { int x[2], r, id; } p[MAX_N];

struct Node {

	int mn[2], mx[2], ls, rs;

	Point tp;

} t[MAX_N];

int N, WD, rt, ans[MAX_N], rub[MAX_N], cur, top;

inline bool operator < (const Point &l, const Point &r) { return l.x[WD] < r.x[WD]; }

inline bool cmp(const Point &l, const Point &r) { return (l.r == r.r) ? (l.id < r.id) : (l.r > r.r); }

int newnode() {

	if (top) return rub[top--];

	else return ++cur;

}

void pushup(int o) {

	int ls = t[o].ls, rs = t[o].rs;

	for (int i = 0; i <= 1; i++) {

		int r = t[o].tp.r;

		t[o].mx[i] = t[o].tp.x[i] + r; t[o].mn[i] = t[o].tp.x[i] - r;

		if (ls) chkmax(t[o].mx[i], t[ls].mx[i]), chkmin(t[o].mn[i], t[ls].mn[i]);

		if (rs) chkmax(t[o].mx[i], t[rs].mx[i]), chkmin(t[o].mn[i], t[rs].mn[i]);

	}

}

int build(int l, int r, int wd) {

	if (l > r) return 0;

	int mid = (l + r) >> 1, o = newnode();

	WD = wd, nth_element(&p[l], &p[mid], &p[r + 1]), t[o].tp = p[mid];

	t[o].ls = build(l, mid - 1, wd ^ 1), t[o].rs = build(mid + 1, r, wd ^ 1);

	return pushup(o), o;

}

bool chk1(int o, Point tmp) { return sqr(tmp.x[0] - t[o].tp.x[0]) + sqr(tmp.x[1] - t[o].tp.x[1]) <= sqr(tmp.r + t[o].tp.r); }

bool chk2(int o, Point tmp) {

	int x0 = tmp.x[0], x1 = tmp.x[1], r = tmp.r;

	if (x0 + r < t[o].mn[0]) return 1;

	if (x0 - r > t[o].mx[0]) return 1;

	if (x1 + r < t[o].mn[1]) return 1;

	if (x1 - r > t[o].mx[1]) return 1;

	return 0;

}

void query(int o, Point tmp) {

	if (chk2(o, tmp)) return ;

	if (!ans[t[o].tp.id] && chk1(o, tmp)) ans[t[o].tp.id] = tmp.id;

	if (t[o].ls) query(t[o].ls, tmp);

	if (t[o].rs) query(t[o].rs, tmp);

}

int main () {

	N = gi();

	for (int i = 1; i <= N; i++) p[i].x[0] = gi(), p[i].x[1] = gi(), p[i].r = gi(), p[i].id = i;

	rt = build(1, N, 0);

	sort(p + 1, p + N + 1, cmp);

	for (int i = 1; i <= N; i++) if (!ans[p[i].id]) query(rt, p[i]);

	for (int i = 1; i <= N; i++) printf("%d ", ans[i]);

	printf("\n");

	return 0;

}