「APIO2018」选圆圈

传送门

Description

Solution 

Code 

#include<bits/stdc++.h>

#define ll long long

#define db double

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define reg register

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

const int MN=3e5+5;

const db eps=1e-3,thi=acos(-1.)/5.,inf=1e12;

int N,D;

db sq(db x){return x*x;}

struct Point

{

	db d[2],mx[2],mn[2];int R,l,r,id;

    db& operator[](int x){return d[x];}

    bool operator<(const Point&x)const{return d[D]<x.d[D];}

}a[MN];

bool cmp(Point x,Point y){return x.R>y.R||(x.R==y.R&&x.id<y.id);}

int rt,ans[MN];

struct K_D_Tree{

	Point p[MN],T;

	void up(int x)

	{

		int l=p[x].l,r=p[x].r;

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

		{

			if(l) p[x].mn[i]=min(p[x].mn[i],p[l].mn[i]),

                  p[x].mx[i]=max(p[x].mx[i],p[l].mx[i]);

            if(r) p[x].mn[i]=min(p[x].mn[i],p[r].mn[i]),

                  p[x].mx[i]=max(p[x].mx[i],p[r].mx[i]);

		}

	}

    int build(int l,int r,int th)

    {

    	if(l>r) return 0;

        reg int mid=(l+r)>>1;D=th;

        std::nth_element(a+l,a+mid,a+r+1);p[mid]=a[mid];

        for(reg int i=0;i<2;++i) p[mid].mx[i]=a[mid][i]+a[mid].R,p[mid].mn[i]=a[mid][i]-a[mid].R;

        p[mid].l=build(l,mid-1,th^1);p[mid].r=build(mid+1,r,th^1);up(mid);

        return mid;

    }

    void query(int x)

    {

    	for(int i=0;i<2;++i) if(T[i]-T.R>p[x].mx[i]||T[i]+T.R<p[x].mn[i]) return;

    	if(!ans[p[x].id])

    	{

    		db dis=sq(T.R+p[x].R),res=0.;

    		for(int i=0;i<2;++i) res+=sq(p[x][i]-T[i]);

    		if(res-dis<eps) ans[p[x].id]=T.id;

		}

    	if(p[x].l)query(p[x].l);if(p[x].r)query(p[x].r);

	}

}kdtree;

int main()

{

	N=read();

	reg int i,x,y;

	for(i=1;i<=N;++i)

	{

		x=read(),y=read();

		a[i][1]=(db)x*sin(thi)+(db)y*cos(thi);a[i][0]=(db)x*cos(thi)-(db)y*sin(thi);

		a[i].R=read();a[i].id=i;

	}

	rt=kdtree.build(1,N,0);

	std::sort(a+1,a+N+1,cmp);

	for(i=1;i<=N;++i)if(!ans[a[i].id])

		kdtree.T=a[i],kdtree.query(rt);

	for(i=1;i<=N;++i) printf("%d ",ans[i]);

	return 0;

}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！