Rockdu's Blog

地址：https://loj.ac/problem/2586

 说一说我和这道题的故事吧。

打完T1的5分后我又来看到了T2。

一看完了又不会，赶快打了个7分暴力。

再想想，我貌似可以拿Subtask2的12分，准备打完T1来码。

然后T1的400个set死活打不出来……于是乎这道题是彻底凉了。

一下来就听见很多人码了个KD-tree爆艹T2，什么鬼？？？？

不过正解貌似是个线段树维护扫描线，没人写……

然后为了练习KDtree，今天又搬出这道题来。

思路大概是一个节点维护能框住下面所有圆的最小矩形。

嗯……就是把圆并近似成矩形判相交剪枝然后骗分。

这个做法在考场上就能得到87分，都怪当年太菜，KDtree都打不熟啊。

那么要拿100分怎么做呢？我们把每个点随机转一个角度就行了。

虽然说是随机但是还是建议取一个sin和cos是特殊值的角，很卡精度。

#include<cstdio>
#include<algorithm>
#include<cmath>
#define eps (1e-4)
using namespace std;
const int maxn = 3e5 + 5;
const double Pi = acos(-1);
#define sqr(x) (1.0 * (x) * (x))

struct Circle {
	double pos[2], mx[2], mn[2];
	int id, r;
	void Spin() {
		double x = pos[0] * 0.6 - pos[1] * 0.8;
		double y = pos[0] * 0.8 + pos[1] * 0.6;
		pos[0] = x, pos[1] = y;
	}
	void init() {
		for(int i = 0; i < 2; ++i) 
			mx[i] = pos[i] + r, mn[i] = pos[i] - r;
	}
} cir[maxn];
int n, ans[maxn];

bool cmp(const Circle &A, const Circle &B) {
	return A.r == B.r ? A.id < B.id : A.r > B.r;
}

namespace KD_tree {
	struct node {
		double mx[2], mn[2], pos[2];
		int del, alldel, ch[2], id, r;
	} t[maxn << 1];
	const int L = 0, R = 1;
	int root = 1, cnt = 1, D = 0;
	int sgn(double x) {return (x > -eps) - (x < eps);}
	void init(int rt) {
		if(!t[rt].del) {
			t[rt].mn[0] = t[rt].pos[0] - t[rt].r, t[rt].mx[0] = t[rt].pos[0] + t[rt].r;
			t[rt].mn[1] = t[rt].pos[1] - t[rt].r, t[rt].mx[1] = t[rt].pos[1] + t[rt].r;
		}
	}
	void push_up(int rt) {
		init(rt);
		t[rt].alldel = t[t[rt].ch[L]].alldel & t[t[rt].ch[R]].alldel & t[rt].del;
		for(register int s = 0; s < 2; ++s) {
			if(!t[rt].ch[s] || t[t[rt].ch[s]].alldel) continue;
			for(register int i = 0; i < 2; ++i) {
				t[rt].mn[i] = min(t[rt].mn[i], t[t[rt].ch[s]].mn[i]);
				t[rt].mx[i] = max(t[rt].mx[i], t[t[rt].ch[s]].mx[i]);
			}
		}
	}
	bool cmp(const Circle & A, const Circle & B) {
		return A.pos[D] < B.pos[D];
	}
	void build(int l, int r, int & rt, int T) {
		if(!rt) rt = ++cnt;
		int mid = l + r >> 1;D = T;
		nth_element(cir + l, cir + mid, cir + r + 1, cmp);
		t[rt].pos[0] = cir[mid].pos[0];
		t[rt].pos[1] = cir[mid].pos[1];
		t[rt].id = cir[mid].id, t[rt].r = cir[mid].r;
		if(l < mid) build(l, mid - 1, t[rt].ch[L], T ^ 1);
		if(mid < r) build(mid + 1, r, t[rt].ch[R], T ^ 1);
		push_up(rt);
	}
	int is_cross(int x, int rt) {
		int flag = 1;
		for(int i = 0; i < 2; ++i) {
			flag &= (sgn(cir[x].mx[i] - t[rt].mn[i]) >= 0 && sgn(t[rt].mx[i] - cir[x].mn[i]) >= 0);
		}
		return flag;
	}
	int is_con(int x, int rt) {
		if(sgn(sqr(cir[x].pos[0] - t[rt].pos[0]) + sqr(cir[x].pos[1] - t[rt].pos[1])
		 - sqr(t[rt].r + cir[x].r)) <= 0)
			return 1;
		return 0;
	}
	void Delete(int x, int rt) {
		if(!is_cross(x, rt) || t[rt].alldel) return ;
		if(is_con(x, rt) && !t[rt].del) {
			t[rt].del = 1;
			ans[t[rt].id] = cir[x].id;
		}
		if(t[rt].ch[R]) Delete(x, t[rt].ch[R]);
		if(t[rt].ch[L]) Delete(x, t[rt].ch[L]);
		push_up(rt);
	}
}

 //记得circle初始化 和id 
int main() {
	using namespace KD_tree;
	//freopen("32", "r", stdin);
	//freopen("test.out", "w", stdout);
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i) {
		scanf("%lf%lf%d", &cir[i].pos[0], &cir[i].pos[1], &cir[i].r);
		cir[i].id = i, cir[i].Spin(), cir[i].init();
	}
	build(1, n, root, 0);
	sort(cir + 1, cir + n + 1, ::cmp);
	for(register int i = 1; i <= n; ++i) {
		if(!ans[cir[i].id]) Delete(i, 1);
	}
	for(register int i = 1; i <= n; ++i)
		printf("%d ", ans[i]);
	return 0;
}