Submission #134923

#	Time	Username	Problem	Language	Result	Execution time	Memory
134923		Lawliet	Circle selection (APIO18_circle_selection)	C++14	0 / 100	326 ms	19776 KiB

circle_selection

#include <bits/stdc++.h>

#define MAX 5010
#define R first.first
#define X second.first
#define Y second.second

using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef pair<pii,pii> circle;

int n;
int n1, n2, n3, n4;

int removed[MAX];

vector<circle> v;

bool intersect(int i, int j)
{
	lli sR = v[i].R + v[j].R; sR = -sR;
	lli dX = v[i].X - v[j].X;
	lli dY = v[i].Y - v[j].Y;

	return (dX*dX <= (sR + dY)*(sR - dY));
}

int main()
{
	scanf("%d",&n);

	memset(removed , -1 , sizeof(removed));

	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%d %d %d",&n1,&n2,&n3);

		circle k;

		k = {{-n3 , g} , {n1 , n2}};

		v.push_back( k );
	}	

	sort(v.begin() , v.end());

	for(int g = 0 ; g < n ; g++)
	{
		int curInd = v[g].first.second;

		if(removed[curInd] != -1) continue;

		for(int h = g ; h < n ; h++)
		{
			if(intersect(g , h))
			{
				int ind = v[h].first.second;

				removed[ind] = curInd;
			}
		}
	}

	for(int g = 1 ; g <= n ; g++)
		printf("%d ",removed[g]);
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
circle_selection.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&n1,&n2,&n3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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