P4631 [APIO2018] 选圆圈

LimpidSlirm · 2023-11-01 22:20:27 · 个人记录

题意

给定平面上 n 个圆，每次选择半径最大的圆，将与其相交或相切的圆全部删去，输出每个圆是被哪个圆删去的。

Solution

显然地，有 \mathcal{O}(n^2) 做法，枚举两个圆，并 \mathcal{O}(1) 判断它们是否相交或相切，即 \sqrt{(x_a-x_b)^2+(y_a-y_b)^2} 是否小于等于 r_a+r_b。

稍微剪一下枝，比如维护每个圆的最左端点和最右端点的坐标，然后对于当前圆的左右端点，在数轴上直接二分出区间然后暴力判断是否可以删去即可，时间复杂度 \mathcal{O}(Can\ Be\ Accepted)。

code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int res=0,flag=1;
    char ch=getchar();
    while(!('0'<=ch&&ch<='9')) (ch=='-')?flag=-1:1,ch=getchar();
    while(('0'<=ch&&ch<='9')) res=res*10+ch-'0',ch=getchar();
    return res*flag;
}
struct circle
{
    int x,y,r;
}; 
struct circle data[300010];
int n;
int ans[300010];
pair<int,int> pos[600010],cir[300010];
long long square(int val)
{
    return val*1ll*val;
}
bool check(int a,int b)
{
    return square(data[a].x-data[b].x)+square(data[a].y-data[b].y)<=square(data[a].r+data[b].r);
}
void solve(int l,int r,int id)
{
    for(int i=lower_bound(pos+1,pos+2*n+1,make_pair(l,0))-pos;i<=2*n&&pos[i].first<=r;i++)
    {
        if(ans[pos[i].second]!=0)
            continue;
        if(check(id,pos[i].second)==true)
            ans[pos[i].second]=id;
    }
    return ;
}
int main(int argc,const char *argv[])
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        data[i].x=read(),data[i].y=read();
        data[i].r=read();
        cir[i]=make_pair(data[i].r,i);
        pos[(i<<1)-1]=make_pair(data[i].x-data[i].r,i);
        pos[i<<1]=make_pair(data[i].x+data[i].r,i);
    }
    std::sort(cir+1,cir+n+1,[](pair<int,int> a,pair<int,int> b){return (a.first==b.first)?a.second<b.second:a.first>b.first;});
    std::sort(pos+1,pos+2*n+1);
    for(int i=1;i<=n;i++)
    {
        int id=cir[i].second;
        if(ans[id]!=0)
            continue;
        solve(data[id].x-data[id].r,data[id].x+data[id].r,id);
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}