洛谷 P4631 【APIO2018】Circle selection 选圆圈 题解

洛谷 P4631 【APIO2018】Circle selection 选圆圈 题解

xiaoh 2020-5-3

题意

平面上有nn个圆(1n3×1051\leq n\leq 3\times 10^5,xi,yi109x_i,y_i\leq 10^9,1r1091\leq r\leq 10^9),我们将其按照半径为第一关键字,编号为第二关键字排序(编号不随排序改变),从前往后选取排序后的点,删除与其不外离的所有圆.求每个圆是被编号为多少的圆删去的.

题解

听说题解是计算几何+CDQCDQ做的?反正我不会就对了QAQ

那么对于除了数据结构一无是处的普通人来说,这道题该怎么做呢?既然是平面上的点,那么我们自然而然的想到了KDK-D TreeTree.考虑如何将圆的位置关系转化为矩形的位置关系.不难想到可以将一颗子树的所有圆的外切矩形作为维护的空间划分(KDK-D TreeTree本质上就是一个靠剪枝吃饭的超级暴力的数据结构,因此就算维护的矩形有重合也不会出锅).既然靠剪枝吃饭,所以我们自然需要剪枝.如果一个节点的外切矩形与询问的圆的外切矩形无公共点,则这棵子树必定没有可以删除的东西,可以跳过.直接维护即可.(不过本题似乎用了替罪羊的RebuildRebuild之后更慢了?反正笔者不建议各位重建树).时间复杂度O(nlognO(n\log n~nn)n\sqrt n).

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(register T &x)
{
	x=0;
	register int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(register T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=300010;
const long long inf=3e10;
int n;
struct circle{
    long long p[2],d;//p为坐标,d为半径
    int id;//编号
}a[MAXN];
int b[MAXN];
struct node{
    int l,r;//左右儿子
    long long p[2],d;//p为坐标
    long long minn[2],maxn[2];//外切矩形的横纵坐标
}f[MAXN];
bool d;
inline bool ccmp(register int a,register int b)//nth_element的cmp函数
{
	return d? f[a].p[0]<f[b].p[0]:f[a].p[1]<f[b].p[1];
}
inline void pushup(register int p)
{
    for(register int i=0;i<2;++i)
    f[p].minn[i]=min(f[p].p[i]-f[p].d,min(f[f[p].l].minn[i],f[f[p].r].minn[i])),
    f[p].maxn[i]=max(f[p].p[i]+f[p].d,max(f[f[p].l].maxn[i],f[f[p].r].maxn[i]));
}
int tmp[MAXN];
int build(register int l,register int r)//二分建树
{
    if(l>=r) return 0;
    register int mid=(l+r)>>1;
	nth_element(tmp+l,tmp+mid,tmp+r,ccmp);
    register int x=tmp[mid];
	d^=1;
    f[x].l=build(l,mid),f[x].r=build(mid+1,r);
	d^=1;
    pushup(x);
    return x;
}
inline bool check(register node a,register circle b)//检查外界矩形是否有交点
{
    return a.minn[0]<=b.p[0]+b.d&&b.p[0]-b.d<=a.maxn[0]&&a.minn[1]<=b.p[1]+b.d&&b.p[1]-b.d<=a.maxn[1];
}
inline long long dist(register node a,register circle b)//两点欧氏距离的平方
{
    return (a.p[0]-b.p[0])*(a.p[0]-b.p[0])+(a.p[1]-b.p[1])*(a.p[1]-b.p[1]);
}
inline bool check_point(register node a,register circle b)//检查两圆是否有交集
{
    return dist(a,b)<=(a.d+b.d)*(a.d+b.d);
}
int ans[MAXN];
void query(register int p,register circle x,register int id)//递归查询
{
    if(!p) return;
    if(!ans[p]&&check_point(f[p],x)) ans[p]=id;
    if(check(f[f[p].l],x)) query(f[p].l,x,id);
    if(check(f[f[p].r],x)) query(f[p].r,x,id);
}
int tot=0;
inline int New(register long long x,register long long y,register long long d)//新建节点的初始化
{
    ++tot;
    f[tot].p[0]=f[tot].maxn[0]=f[tot].minn[0]=x;
    f[tot].p[1]=f[tot].maxn[1]=f[tot].minn[1]=y;
	f[tot].d=d;
    return tot;
} 
inline bool cmp(int u,int v)//圆的排序
{
    return a[u].d>a[v].d;
}
int rt=0;
int main()
{
    f[0].minn[0]=f[0].minn[1]=inf;//初始化边界
    f[0].maxn[0]=f[0].maxn[1]=-inf;
    read(n);
    for(register int i=1;i<=n;++i) read(a[i].p[0]),read(a[i].p[1]),read(a[i].d),a[i].id=i,tmp[i-1]=New(a[i].p[0],a[i].p[1],a[i].d),b[i]=i;
    stable_sort(b+1,b+n+1,cmp);//由于有编号这一第二关键字排序,因此需要稳定排序
	d=1;
    rt=build(0,n);
    for(register int i=1;i<=n;++i)
    if(!ans[b[i]]) query(rt,a[b[i]],a[b[i]].id);
    for(register int i=1;i<=n;++i) write(ans[i]),putchar(' ');
    putchar('\n');
	return 0;
}

后记

自从春节十二响被可恶的你谷管理员一刀削入紫题后,这算是我严格意义上过的第一道黑题(以后也会变紫?)以及第一道APIOAPIO的题,值得庆祝一下QAQ

敲代码时脑子抽筋先是删点时没有判断是否已被删去,调试时间+2h+2h……然后又没有看见负坐标,把00minnminn搞成了00,卡常时间+2h+2h……两天以后,又是一条好汉QAQ