Submission #112085

#	Time	Username	Problem	Language	Result	Execution time	Memory
112085		jaberndc	Circle selection (APIO18_circle_selection)	C++14	0 / 100	7 ms	856 KiB

circle_selection

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int ans[3005];
struct circle
{
	int x,y,r,i;
	int used=0;
};
bool comp(circle a,circle b)
{
	if(a.r==b.r) return a.i<b.i;
	return a.r>b.r;
}

circle c[3005];
bool intrsct(circle a,circle b)
{
	double d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
	if(d<=a.r+b.r) return true;
	return false;
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i].x>>c[i].y>>c[i].r;
		c[i].i=i;
	}
	sort(c+1,c+n+1,comp);
	for(int i=1;i<=n;i++)
	{
		if(c[i].used) continue;
		ans[c[i].i]=c[i].i;
		c[i].used=1;
		int start=i+1;
		for(int j=start;j<=n;j++)
		{
			if(c[j].used) continue;
			if(intrsct(c[i],c[j]))
			{
				//cout<<c[j].i<<endl;
				ans[c[j].i]=c[i].i;
				c[j].used=1;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<" ";
	}
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13