「LOJ 2586」「APIO2018」选圆圈

LOJ #2586

题意

平面上有$n$个圆，编号$1..n$

重复如下操作直到不存在圆

1. 选择一个半径最大的圆，如果有多个，选择编号最小的

2. 把所有与第1步选出的圆有交的圆删除

其中两个圆有交当且仅当存在一个点，这个点同时被两个圆包含，包含定义为点在圆内或者圆上

$n\le 3*10^5$

---

做法

现场在划水，现在补题不知道正解了也找不到，应该也不会。

直接按照圆心坐标建k-d tree

一个点维护子树中圆的四个方向的坐标极值，也就是一个矩形

每次挑一个优先的圆去遍历树

如果圆与当前的矩形无交就可以退出了

这样可以获得 $87$ 分的好成绩

然后把所有坐标旋转一个角度就能过了

• $eps$ 不能设到 $10^{-5}$ 那么小..

• 逆时针旋转角 $\alpha$ 可以理解为一个线性变换

$$
\begin{bmatrix}
\cos \alpha & -\sin \alpha \
\sin \alpha & \cos \alpha
\end{bmatrix}
\begin{pmatrix}
x \
y
\end{pmatrix}

\begin{pmatrix}
x’ \
y’
\end{pmatrix}
$$

最坏时间复杂度$\mathcal O(n^2)$

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 300005;
const double sina=sqrt(2)/2, cosa=sina, eps=1e-3;
int n, D, now, root, ans[N], b[N], f[N], ch[N][2];
double mn[N][2], mx[N][2];
bool del[N];
struct circle{
	int r, id;
	double s[2];
	inline bool operator <(const circle &rhs)const{ return r>rhs.r;}
}anow, a[N];
inline void update(int t){
	mn[t][0]=a[t].s[0]-a[t].r, mn[t][1]=a[t].s[1]-a[t].r;
	mx[t][0]=a[t].s[0]+a[t].r, mx[t][1]=a[t].s[1]+a[t].r;
	for(int i=0; i<2; ++i) if(ch[t][i]) for(int j=0; j<2; ++j)
		mx[t][j]=max(mx[t][j], mx[ch[t][i]][j]),
		mn[t][j]=min(mn[t][j], mn[ch[t][i]][j]);
}
inline bool cmp(const circle &x, const circle &y){ return x.s[D]<y.s[D];}
void build(int &t, int l, int r, int k){
	if(l>r) return;
	int mid=l+r>>1;
	t=mid, D=k, nth_element(a+l, a+mid, a+r+1, cmp);
	build(ch[t][0], l, mid-1, k^1), build(ch[t][1], mid+1, r, k^1), update(t);
}
inline double sqr(double x){ return x*x;}
void erase(int t, int k){
	if(!t || anow.s[0]-anow.r>mx[t][0] || anow.s[1]-anow.r>mx[t][1] ||
		anow.s[0]+anow.r<mn[t][0] || anow.s[1]+anow.r<mn[t][1]) return;
	if(!del[t])
		if(sqr(a[t].s[0]-anow.s[0])+sqr(a[t].s[1]-anow.s[1])<=sqr(a[t].r+anow.r)+eps)
			del[t]=1, ans[a[t].id]=anow.id, a[t].s[0]=a[t].s[1]=0, a[t].r=-2e9;
	erase(ch[t][0], k^1), erase(ch[t][1], k^1), update(t);
}
int main() {
	read(n);
	for(int i=1; i<=n; ++i){
		int x, y;
		read(x), read(y), read(a[i].r), a[i].id=i;
		a[i].s[0]=x*cosa-y*sina, a[i].s[1]=x*sina+y*cosa;
	}
	stable_sort(a+1, a+n+1);
	for(int i=1; i<=n; ++i) b[a[i].id]=i;
	build(root, 1, n, 0);
	for(int i=1; i<=n; ++i) f[b[a[i].id]]=i;
	for(int i=1; i<=n; ++i) if(!del[now=f[i]]) anow=a[now], erase(root, 0);
	for(int i=1; i<=n; ++i) print(ans[i]), print(' ');
	return flush(), 0;
}