description

洛谷

data range

\[ n\le 3\times 10^5\]

solution

\(kd-tree\)乱搞大法好

一道拿矩形框圆的好题

如果修改的圆形和矩形没有交就返回

剪枝十分优秀

转了个角度防止被卡

code

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define Cpy(x,y) memcpy(x,y,sizeof(x))
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef long double dd;
const dd eps=1e-6;
const int mod=998244353;
const int N=300010;
const dd pi=acos(-1);
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
const dd angel=pi/5;
il ll read(){
    RG ll data=0,w=1;RG char ch=getchar();
    while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘))ch=getchar();
    if(ch==‘-‘)w=-1,ch=getchar();
    while(ch<=‘9‘&&ch>=‘0‘)data=data*10+ch-48,ch=getchar();
    return data*w;
}

il void file(){
    srand(time(NULL)+rand());
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
}

int n,rt,tot,cd,ans[N],ra,now;dd d[2];
struct circle{dd d[2];int ra,id;}c[N];
bool operator <(circle a,circle b){return a.d[cd]<b.d[cd];}
bool cmp_ra(circle a,circle b){
    if(a.ra!=b.ra)return a.ra>b.ra;return a.id<b.id;
}
struct kdnode{dd d[2],l[2],r[2];int ra,s[2],id;}t[N];
#define ls t[i].s[0]
#define rs t[i].s[1]
#define mid ((l+r)>>1)
il void update(int i){
    for(RG int k=0;k<2;k++){
        t[i].l[k]=t[i].d[k]-t[i].ra;t[i].r[k]=t[i].d[k]+t[i].ra;
        if(ls){
            t[i].l[k]=min(t[i].l[k],t[ls].l[k]);
            t[i].r[k]=max(t[i].r[k],t[ls].r[k]);
        }
        if(rs){
            t[i].l[k]=min(t[i].l[k],t[rs].l[k]);
            t[i].r[k]=max(t[i].r[k],t[rs].r[k]);
        }
    }   
}

int build(int l,int r,int D){
    if(l>r)return 0;
    cd=D;nth_element(c+l,c+mid,c+r+1);
    Cpy(t[mid].d,c[mid].d);
    t[mid].ra=c[mid].ra;t[mid].id=c[mid].id;
    t[mid].s[0]=build(l,mid-1,D^1);
    t[mid].s[1]=build(mid+1,r,D^1);
    update(mid);return mid;
}

#define sqr(x) ((x)*(x))
il bool calc(int i){
    RG dd ret=0;
    if(d[0]<t[i].l[0]||t[i].r[0]<d[0])
        ret+=min(sqr(d[0]-t[i].l[0]),sqr(d[0]-t[i].r[0]));
    if(d[1]<t[i].l[1]||t[i].r[1]<d[1])
        ret+=min(sqr(d[1]-t[i].l[1]),sqr(d[1]-t[i].r[1]));
    return 1ll*ra*ra-ret<eps;
}
void modify(int i){
    if(!i||calc(i))return;
    if(!ans[t[i].id]&&sqr(t[i].d[0]-d[0])+sqr(t[i].d[1]-d[1])-sqr((ll)(t[i].ra+ra))<eps)
        ans[t[i].id]=now;
    modify(ls);modify(rs);
}

int main()
{
    n=read();
    for(RG int i=1,x,y;i<=n;i++){
        x=read();y=read();
        c[i].d[0]=x*cos(angel)-y*sin(angel);
        c[i].d[1]=x*sin(angel)+y*cos(angel);
        c[i].ra=read();c[i].id=i;
    }
    rt=build(1,n,0);sort(c+1,c+n+1,cmp_ra);
    for(RG int i=1;i<=n;i++)
        if(!ans[c[i].id]){
            ans[c[i].id]=now=c[i].id;Cpy(d,c[i].d);ra=c[i].ra;
            modify(rt);
        }
    for(RG int i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}

[APIO2018] Circle selection 选圆圈

原文：https://www.cnblogs.com/cjfdf/p/9664510.html