欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ5462: [APIO2018] 新家(K-D Tree)

程序员文章站 2023-11-17 22:40:46
题意 "题目链接" Sol 下面是错误做法,正解请看 "这里" 考虑直接用K D tree模拟。。 刚开始想的是维护矩形最大最小值,以及子树中最大圆的位置,然后。。。 实际上最大圆的位置是不用维护的,直接把原序列排一遍序就可以了 再努力卡卡常就过了 如果还过不了的话可以尝试把所有点都转一个角度 cp ......

题意

题目链接

sol

下面是错误做法,正解请看

考虑直接用k-d tree模拟。。

刚开始想的是维护矩形最大最小值,以及子树中最大圆的位置,然后。。。

BZOJ5462: [APIO2018] 新家(K-D Tree)

实际上最大圆的位置是不用维护的,直接把原序列排一遍序就可以了

再努力卡卡常就过了

如果还过不了的话可以尝试把所有点都转一个角度

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define chmin(x, y) (x = x < y ? x : y)
#define chmax(x, y) (x = x > y ? x : y)
#define ls(x) t[k].ls
#define rs(x) t[k].rs
#define double long double 
const double alpha(acos(-1) / 5);
const double cosa(cos(alpha));
const double sina(sin(alpha));
using namespace std;
const int maxn = 1e6 + 10;
const double inf = 1e12 + 10, eps = 1e-11;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, wd, root, tot, num, ans[maxn];
struct point {
    double x[2], r;
    int id;
    bool operator < (const point &rhs) const {
        return rhs.x[wd] - x[wd] > eps; 
    }
    double operator [] (const int d) {
        return x[d];
    }
}p[maxn];
int comp(const point &a, const point b) {
    return a.r == b.r ? a.id < b.id : a.r > b.r;
}
struct node {
    int ls, rs, id;
    double mx[2], mi[2];
    point p;
}t[maxn];
void update(int k) {
    for(int i = 0; i <= 1; i++) {
        if(!ans[t[k].id]) t[k].mi[i] = t[k].p[i] - t[k].p.r, t[k].mx[i] = t[k].p[i] + t[k].p.r;
        else t[k].mi[i] = inf, t[k].mx[i] = -inf;
        if(ls(k)) chmin(t[k].mi[i], t[ls(k)].mi[i]), chmax(t[k].mx[i], t[ls(k)].mx[i]);
        if(rs(k)) chmin(t[k].mi[i], t[rs(k)].mi[i]), chmax(t[k].mx[i], t[rs(k)].mx[i]);
    }   
}
int build(int l, int r, int wd) {
    if(l > r) return 0;
    wd = wd; int mid = (l + r) >> 1, k = ++tot;
    nth_element(p + l, p + mid, p + r + 1);
    t[k].p = p[mid];  t[k].id = p[mid].id; 
    t[k].ls = build(l, mid - 1, wd ^ 1) ;
    t[k].rs = build(mid + 1, r, wd ^ 1);
    update(k);
    return k;
}
double sqr(double x) {
    return x * x;
}
bool judge(point a, point b) {
    double tmp = sqr(a[0] - b[0]) + sqr(a[1] - b[1]);
    return sqr(a.r + b.r) + eps - tmp > 0;
}
bool pd(int k, point a) {
    for(int i = 0; i <= 1; i++) 
        if((a[i] + a.r + eps < t[k].mi[i]) || (a[i] - a.r - eps > t[k].mx[i])) return 1;
    
    return 0;
}
void delet(int k, point a) {
    if(pd(k, a)) return ;
    if(!ans[t[k].id] && judge(t[k].p, a)) ans[t[k].id] = a.id, t[k].p.r = -inf, num++;
    if(ls(k)) delet(ls(k), a);
    if(rs(k)) delet(rs(k), a);
    update(k);
}
int main() {
    //freopen("a.in", "r", stdin);
    n = read();
    for(int i = 1; i <= n; i++) {
        double x = read(), y = read(), tx = x * cosa - y * sina, ty = x * sina + y * cosa;
        p[i].x[0] = x; p[i].x[1] = y; p[i].r = read(), p[i].id = i;
    }
    root = build(1, n, 0);
    sort(p + 1, p + n + 1, comp);
    for(int i = 1; i <= n; i++) if(!ans[p[i].id]) delet(root, p[i]);
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}