洛谷 P4631 【APIO2018】Circle selection 选圆圈 题解
xiaoh 2020-5-3
题意
平面上有个圆(,,),我们将其按照半径为第一关键字,编号为第二关键字排序(编号不随排序改变),从前往后选取排序后的点,删除与其不外离的所有圆.求每个圆是被编号为多少的圆删去的.
题解
听说题解是计算几何+做的?反正我不会就对了QAQ
那么对于除了数据结构一无是处的普通人来说,这道题该怎么做呢?既然是平面上的点,那么我们自然而然的想到了 .考虑如何将圆的位置关系转化为矩形的位置关系.不难想到可以将一颗子树的所有圆的外切矩形作为维护的空间划分( 本质上就是一个靠剪枝吃饭的超级暴力的数据结构,因此就算维护的矩形有重合也不会出锅).既然靠剪枝吃饭,所以我们自然需要剪枝.如果一个节点的外切矩形与询问的圆的外切矩形无公共点,则这棵子树必定没有可以删除的东西,可以跳过.直接维护即可.(不过本题似乎用了替罪羊的之后更慢了?反正笔者不建议各位重建树).时间复杂度~.
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;
}
后记
自从春节十二响被可恶的你谷管理员一刀削入紫题后,这算是我严格意义上过的第一道黑题(以后也会变紫?)以及第一道的题,值得庆祝一下QAQ
敲代码时脑子抽筋先是删点时没有判断是否已被删去,调试时间……然后又没有看见负坐标,把的搞成了,卡常时间……两天以后,又是一条好汉QAQ