Submission #111873

#	Time	Username	Problem	Language	Result	Execution time	Memory
111873		square1001	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3021 ms	15704 KiB

circle_selection

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class point2d {
	public:
	long long x, y;
	point2d() : x(0), y(0) {};
	point2d(long long x_, long long y_) : x(x_), y(y_) {};
	point2d& operator+=(const point2d& p) { x += p.x; y += p.y; return *this; }
	point2d& operator-=(const point2d& p) { x -= p.x; y -= p.y; return *this; }
	point2d operator+(const point2d& p) const { return point2d(*this) += p; }
	point2d operator-(const point2d& p) const { return point2d(*this) -= p; }
	long long norm() const { return x * x + y * y; }
};
int main() {
	int n;
	cin >> n;
	vector<point2d> p(n);
	vector<long long> r(n);
	for(int i = 0; i < n; ++i) {
		cin >> p[i].x >> p[i].y >> r[i];
	}
	vector<int> ans(n, -1);
	while(true) {
		int ptr = -1; long long radius = -1;
		for(int i = 0; i < n; ++i) {
			if(ans[i] != -1) continue;
			if(radius < r[i]) {
				radius = r[i];
				ptr = i;
			}
		}
		if(ptr == -1) break;
		for(int i = 0; i < n; ++i) {
			if(ans[i] == -1 && (p[ptr] - p[i]).norm() <= 1LL * (r[ptr] + r[i]) * (r[ptr] + r[i])) {
				ans[i] = ptr;
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		if(i) cout << ' ';
		cout << ans[i] + 1;
	}
	cout << endl;
	return 0;
}

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