제출 #112091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112091		jaberndc	원 고르기 (APIO18_circle_selection)	C++14	0 / 100	7 ms	680 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=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	if(d<=(a.r+b.r)*(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