LOJ2586 APIO2018 选圆圈

考前挣扎
KD树好题！
暴力模拟通过kd树的结构把子树内的圈圈框起来
然后排个序根据圆心距 <= R1+R2来判断是否有交点
然后随便转个角度就可以保持优越的nlgn啦
卡精度差评必须写eps差评
//Love and Freedom.

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define db long double

#define inf 20021225

#define ll long long

#define mxn 310000

#define eps 1e-3

using namespace std;

struct poi

{

    db x,y;

    poi(){}

    poi(db _x,db _y){x=_x,y=_y;}

};

struct circle

{

    db r; poi pos; int id;

    circle(){}

    circle(poi _pos,db _r){pos=_pos;r = _r;}

}cc[mxn];

int ans[mxn];

struct node

{

    int son[2],id; //poi p;

    db r,mr,mx[2],mn[2],pos[2];

};

bool flag;

bool cmp(circle a,circle b)

{

    if(flag?abs(a.pos.x - b.pos.x)<eps:abs(a.pos.y-b.pos.y)<eps)	return a.r>b.r;

    return flag?a.pos.x<b.pos.x:a.pos.y<b.pos.y;

}

db dis(poi a,poi b)

{

    return (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y);

}

struct KD

{

    node t[mxn]; int rt;

    void update(int x)

    {

        int l = t[x].son[0];

        int r = t[x].son[1];

        for(int c = 0;c < 2; c++)

        {

            if(l)	t[x].mx[c]=max(t[l].mx[c],t[x].mx[c]),t[x].mn[c]=min(t[l].mn[c],t[x].mn[c]);

            if(r)	t[x].mx[c]=max(t[r].mx[c],t[x].mx[c]),t[x].mn[c]=min(t[r].mn[c],t[x].mn[c]);

        }

        if(l)	t[x].mr=max(t[x].mr,t[l].mr);

        if(r)	t[x].mr=max(t[x].mr,t[r].mr);

    }

    void build(int &x,int l,int r,bool w)

    {

        flag = w; sort(cc+l,cc+r+1,cmp);

        int mid = l+r>>1;	x = mid;

        t[x].mr = t[x].r = cc[mid].r; t[x].id = cc[mid].id;

        for(int c = 0;c < 2;c++)

            t[x].pos[c] = t[x].mn[c] = t[x].mx[c] = c?cc[mid].pos.y:cc[mid].pos.x;

        if(l<mid)	build(t[x].son[0],l,mid-1,w^1);

        if(mid<r)	build(t[x].son[1],mid+1,r,w^1);

        update(x);

    }

    bool del(circle goal, circle tmp)

    {

        if(dis(goal.pos,tmp.pos) - (goal.r+tmp.r)*(goal.r+tmp.r)<=eps)	return true;

        return false;

    }

    db check(int x,circle goal)

    {

        db ans =  0;

        for(int c = 0;c < 2;c++)

        {

            db wz = (c?goal.pos.y:goal.pos.x),tmp;

            if(wz>=t[x].mn[c] && wz<=t[x].mx[c])	tmp = 0;

            else	tmp = min(abs(t[x].mn[c]-wz),abs(t[x].mx[c]-wz));

            ans += tmp*tmp;

        }

        return ans;

    }

    void query(int x,circle goal,int w)

    {

        if(!ans[t[x].id] && del(goal,circle(poi(t[x].pos[0],t[x].pos[1]),t[x].r)))	ans[t[x].id] = w;

        int  l = t[x].son[0], r = t[x].son[1]; db d1,d2;

        if(l)

        {

            d1 = check(l,goal);

            if((t[l].mr+goal.r)*(t[l].mr+goal.r) -d1>= -eps)	query(l,goal,w);

        }

        if(r)

        {

            d2 = check(r,goal);

            if((t[r].mr+goal.r)*(t[r].mr+goal.r) -d2>= -eps)	query(r,goal,w);

        }

    }

}kd;

bool qaq(circle a,circle b)

{

    return abs(a.r-b.r)<eps?a.id<b.id:a.r>b.r;

}

const db phi = 1.05426;

poi rotate(poi a)

{

	return poi(cosl(phi)*a.x-sinl(phi)*a.y,sinl(phi)*a.x+cosl(phi)*a.y);

}

int main()

{

    int n; scanf("%d",&n);

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

    {

        scanf("%Lf%Lf%Lf",&cc[i].pos.x,&cc[i].pos.y,&cc[i].r),cc[i].id=i;

    	cc[i].pos = rotate(cc[i].pos);

    }

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

    sort(cc+1,cc+n+1,qaq);

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

        if(!ans[cc[i].id])

            kd.query(kd.rt,cc[i],cc[i].id);

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

        printf("%d ",ans[i]);

    return 0;

}
巴特西

LOJ2586 APIO2018 选圆圈

最新文章

热门文章
