M_sea

洛谷4631 [APIO2018] Circle selection 选圆圈
LuoguBZOJ分析用$KD-Tree$维护每个圆的横纵坐标范围$[x-r,x+r]$、$[y-r,y+r]$。...
扫描右侧二维码阅读全文
25
2018/12

洛谷4631 [APIO2018] Circle selection 选圆圈

Luogu

BZOJ

分析

用$KD-Tree$维护每个圆的横纵坐标范围$[x-r,x+r]$、$[y-r,y+r]$。

然后从前往后暴力统计答案即可。

一个剪枝:当搜到一个在当前圆的范围外的园,直接跳过。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chmin(int& a,int b) { if (b<a) a=b; }
inline void chmax(int& a,int b) { if (b>a) a=b; }
inline double sqr(int x) { return 1.0*x*x; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=300000+10;
const double EPS=1e-6;

int n,now,root,ans[MAXN];

struct data {
    int d[2],r,id;
    int operator <(const data& rhs) const {
        return d[now]<rhs.d[now];
    }
} a[MAXN];
inline int cmp(data x,data y) {
    if (x.r!=y.r) return x.r>y.r;
    return x.id<y.id;
}
struct node {
    data a;
    int l,r,mn[2],mx[2];
} t[MAXN];
struct KD_Tree {
    inline void upd(int k,int p) {
        chmin(t[k].mn[0],t[p].mn[0]),chmax(t[k].mx[0],t[p].mx[0]);
        chmin(t[k].mn[1],t[p].mn[1]),chmax(t[k].mx[1],t[p].mx[1]);
    }
    inline void pushup(int o) {
        int x=t[o].a.d[0],y=t[o].a.d[1],r=t[o].a.r;
        t[o].mn[0]=x-r,t[o].mx[0]=x+r;
        t[o].mn[1]=y-r,t[o].mx[1]=y+r;
        if (t[o].l) upd(o,t[o].l);
        if (t[o].r) upd(o,t[o].r);
    }
    inline void build(int& o,int l,int r,int tag) {
        int mid=(l+r)>>1; now=tag;
        nth_element(a+l,a+mid+1,a+r+1);
        o=mid,t[o].a=a[mid];
        if (l<mid) build(t[o].l,l,mid-1,tag^1); else t[o].l=0;
        if (r>mid) build(t[o].r,mid+1,r,tag^1); else t[o].r=0;
        pushup(o);
    }
    inline int check(int o,data A) {
        int x=A.d[0],y=A.d[1],r=A.r+t[o].a.r,xx=t[o].a.d[0],yy=t[o].a.d[1];
        return sqr(x-xx)+sqr(y-yy)-sqr(r)<=EPS;
    }
    inline int far(int o,data A) {
        int x=A.d[0],y=A.d[1],r=A.r;
        if (x+r<t[o].mn[0]) return 1;
        if (y+r<t[o].mn[1]) return 1;
        if (x-r>t[o].mx[0]) return 1;
        if (y-r>t[o].mx[1]) return 1;
        return 0;
    }
    inline void query(int o,data A) {
        if (far(o,A)) return;
        if (!ans[t[o].a.id]&&check(o,A)) ans[t[o].a.id]=A.id;
        if (t[o].l) query(t[o].l,A);
        if (t[o].r) query(t[o].r,A);
    }
} T;

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        a[i].d[0]=read(),a[i].d[1]=read(),a[i].r=read(),a[i].id=i;
    T.build(root,1,n,0);
    sort(a+1,a+n+1,cmp);
    for (re int i=1;i<=n;++i)
        if (!ans[a[i].id]) T.query(root,a[i]);
    for (re int i=1;i<=n;++i) printf("%d ",ans[i]);
    putchar('\n');
    return 0;
}
最后修改:2019 年 01 月 09 日 07 : 52 AM

2 条评论

  1. smy

    kdtree大佬%%%

    1. M_sea
      @smy

      您早就会了

发表评论