oj.uz

Submission #112085

# Submission time Handle Problem Language Result Execution time Memory
112085 2019-05-17T11:13:40 Z jaberndc Circle selection (APIO18_circle_selection) C++14
0 / 100
 7 ms 856 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -