「APIO2018选圆圈」

题目描述

在平面上，有 \(n\) 个圆，记为 \(c_1, c_2, \ldots, c_n\) 。我们尝试对这些圆运行这个算法：

1. 找到这些圆中半径最大的。如果有多个半径最大的圆，选择编号最小的。记为 \(c_i\) 。
2. 删除 \(c_i\) 及与其有交集的所有圆。两个圆有交集当且仅当平面上存在一个点，这个点同时在这两个圆的圆周上或圆内。
3. 重复上面两个步骤直到所有的圆都被删除。

当 \(c_i\) 被删除时，若循环中第1步选择的圆是 \(c_j\) ，我们说 \(c_i\) 被 \(c_j\) 删除。对于每个圆，求出它是被哪一个圆删除的。

解题思路 :

越抓越痒有理想，\(n^2\) 有信仰。

首先把圆心拿出来建KD树，对于每一棵子树，维护出一个矩形框住这些圆的并，每次删除爆枚整棵树通过判断和这个矩形有没有交来剪枝，最坏复杂度 \(O(n^2)\) ，好像旋转某个角度就卡不掉了。

话说写APIO题卡评测真是爽啊，顺便写篇博客存个KD树板子。

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

    int f = 0, ch = 0; x = 0;

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

    if(f) x = -x;

}

const int N = 600005;

const double sina = sqrt(2)/2, cosa = sina, eps = 5e-2;

int ans[N], Sgn, rt, n;

inline double sqr(double x){ return x * x; }

inline void chkmax(double &x, double y){ if(y > x) x = y; }

inline void chkmin(double &x, double y){ if(y < x) x = y; }

struct Point{ double x, y, r; int id; } a[N], s[N];

inline bool cmp(Point A, Point B){

	if(Sgn == 0) return A.x < B.x;

	if(Sgn == 1) return A.y < B.y;

	if(Sgn == 2) return A.r == B.r ? (A.id < B.id) : (A.r > B.r);

}

struct Kdtree{

	int ch[N][2];

	struct Node{

		double mx[2], mn[2]; int id;

	}T[N];

	inline void update(int x){

		T[x].mx[0] = a[x].x + a[x].r, T[x].mx[1] = a[x].y + a[x].r;

		T[x].mn[0] = a[x].x - a[x].r, T[x].mn[1] = a[x].y - a[x].r;

		for(int i = 0; i < 2; i++) if(ch[x][i])

			for(int j = 0; j < 2; j++){

				chkmax(T[x].mx[j], T[ch[x][i]].mx[j]);

				chkmin(T[x].mn[j], T[ch[x][i]].mn[j]);

			}

	}

	inline void build(int &u, int l, int r, int sgn){

		if(l > r) return;

		int mid = l + r >> 1; u = mid, Sgn = sgn;

		nth_element(a + l, a + mid, a + r + 1, cmp);

		build(ch[u][0], l, mid - 1, sgn ^ 1);

		build(ch[u][1], mid + 1, r, sgn ^ 1), update(u);

	}

	inline void Delete(int u, Point now){

		if(!u || now.x - now.r > T[u].mx[0] || now.x + now.r < T[u].mn[0]

		|| now.y - now.r > T[u].mx[1] || now.y + now.r < T[u].mn[1]) return;

		if(!ans[a[u].id]){

			if(sqr(now.x-a[u].x)+sqr(now.y-a[u].y) <= sqr(now.r+a[u].r) + eps)

				ans[a[u].id] = now.id, a[u].x = a[u].y = 0, a[u].r = -inf;

		}

		Delete(ch[u][0], now), Delete(ch[u][1], now), update(u);

	}

}van;

int main(){

	read(n);

	for(int i = 1, x, y; i <= n; i++){

		read(x), read(y), read(a[i].r), a[i].id = i;

		a[i].x = (double) x * cosa - y * sina;

		a[i].y = (double) x * sina + y * cosa;

	}

	Sgn = 2, sort(a + 1, a + n + 1, cmp);

	for(int i = 1; i <= n; i++) s[i] = a[i];

	van.build(rt, 1, n, 0);

	for(int i = 1; i <= n; i++)

		if(!ans[s[i].id]) van.Delete(rt, s[i]);

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

	return 0;

}