题面
自己去(LOJ)上找
Sol
直接排序然后(KDTree)查询
然后发现(TLE)了
然后把点旋转一下，就过了。。
# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
const int maxn(3e5 + 5);
const double eps(1e-3);
const double alpha(acos(-1) / 5);
const double cosa(cos(alpha));
const double sina(sin(alpha));
int n, ans[maxn], op, rt;
struct Data{
double d[2], r;
int id;
IL int operator <(RG Data b) const{
return d[op] < b.d[op];
}
} a[maxn];
IL int Cmp(RG Data x, RG Data y){
return x.r != y.r ? x.r > y.r : x.id < y.id;
}
struct KDTree{
double d[2], mn[2], mx[2], r;
int ls, rs, id;
} tr[maxn];
IL void Chkmax(RG double &x, RG double y){
if(y > x) x = y;
}
IL void Chkmin(RG double &x, RG double y){
if(y < x) x = y;
}
IL void Update(RG int x){
tr[x].mn[0] = tr[x].mx[0] = tr[x].d[0];
tr[x].mn[1] = tr[x].mx[1] = tr[x].d[1];
RG int ls = tr[x].ls, rs = tr[x].rs;
if(ls){
Chkmin(tr[x].mn[0], tr[ls].mn[0]), Chkmin(tr[x].mn[1], tr[ls].mn[1]);
Chkmax(tr[x].mx[0], tr[ls].mx[0]), Chkmax(tr[x].mx[1], tr[ls].mx[1]);
}
if(rs){
Chkmin(tr[x].mn[0], tr[rs].mn[0]), Chkmin(tr[x].mn[1], tr[rs].mn[1]);
Chkmax(tr[x].mx[0], tr[rs].mx[0]), Chkmax(tr[x].mx[1], tr[rs].mx[1]);
}
}
IL int Build(RG int l, RG int r, RG int nop){
RG int x = (l + r) >> 1; op = nop;
nth_element(a + l, a + x, a + r + 1);
tr[x].d[0] = a[x].d[0], tr[x].d[1] = a[x].d[1];
tr[x].id = a[x].id, tr[x].r = a[x].r;
if(l < x) tr[x].ls = Build(l, x - 1, nop ^ 1);
if(r > x) tr[x].rs = Build(x + 1, r, nop ^ 1);
Update(x);
return x;
}
# define Sqr(x) ((x) * (x))
IL int Check(RG int x, RG Data p){
RG double x1 = tr[x].d[0], y1 = tr[x].d[1], x2 = p.d[0], y2 = p.d[1], r1 = tr[x].r, r2 = p.r;
return Sqr(x1 - x2) + Sqr(y1 - y2) - eps <= Sqr(r1 + r2);
}
IL int Cut(RG int x, RG Data p){
RG double x2 = p.d[0], y2 = p.d[1], r = p.r + p.r;
if(x2 + r + eps < tr[x].mn[0]) return 1;
if(y2 + r + eps < tr[x].mn[1]) return 1;
if(x2 - r > tr[x].mx[0] + eps) return 1;
if(y2 - r > tr[x].mx[1] + eps) return 1;
return 0;
}
IL void Modify(RG int x, RG Data p){
if(Cut(x, p)) return;
if(!ans[tr[x].id] && Check(x, p)) ans[tr[x].id] = p.id;
if(tr[x].ls) Modify(tr[x].ls, p);
if(tr[x].rs) Modify(tr[x].rs, p);
}
int main(){
n = Input();
for(RG int i = 1; i <= n; ++i){
RG double x = Input(), y = Input(), r = Input();
a[i] = (Data){x * cosa - y * sina, x * sina + y * cosa, r, i};
}
rt = Build(1, n, 0), sort(a + 1, a + n + 1, Cmp);
for(RG int i = 1; i <= n; ++i)
if(!ans[a[i].id]) Modify(rt, a[i]);
for(RG int i = 1; i <= n; ++i) printf("%d ", ans[i]);
return 0;
}