Submission #111810

#TimeUsernameProblemLanguageResultExecution timeMemory
111810b2563125원 고르기 (APIO18_circle_selection)C++14
7 / 100
3098 ms17452 KiB
#include<iostream>
#include<vector>
#include<algorithm>
#define vel vector<long long>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pin pair<int,int>
#define mkp make_pair
#define sor(v) sort(v.begin(),v.end())
#define int long long
int sq(int n) { return n * n; }
int dist(vel &x, vel &y, int i, int j) {
	return sq(x[i] - x[j]) + sq(y[i] - y[j]);
}
signed main() {
	int n; cin >> n;
	vel x(n), y(n), r(n);
	vector<pin> al(n);
	rep(i, n) { cin >> x[i] >> y[i] >> r[i]; al[i] = mkp(-r[i], i); }
	vector<bool> is_kled(n, false);
	vel ans(n);
	sor(al);
	rep(i, n) {
		int ri = al[i].second;
		if (!is_kled[ri]) {
			rep(j, n) {
				if (!is_kled[j] and (dist(x, y, ri, j) <= sq(r[ri] + r[j]) )) {
					ans[j] = ri;
					is_kled[j] = true;
				}
			}
		}
	}
	rep(i, n) { cout << ans[i]+1<<endl; }
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...