Submission #106709

#	Time	Username	Problem	Language	Result	Execution time	Memory
106709		chemistrae03	Circle selection (APIO18_circle_selection)	C++17	0 / 100	4 ms	1380 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

struct Circle {
	int x, y, r, i;
	Circle(int _x, int _y, int _r, int _i) : x(_x), y(_y), r(_r), i(_i) {
		// do nothing
	}
	bool intercept(const Circle &c) {
		int dx = c.x - x, dy = c.y - y, dr = c.r + r;
		// cerr << dx << ' ' << dy << ' ' << dr << '\n';
		if (dx * dx + dy * dy <= dr * dr) {
			return true;
		}
		return false;
	}
	bool operator < (const Circle &c) { 
		return r > c.r;
	}
};

const int MAX = 1e5 + 9;
vector<Circle> v;
int parent[MAX];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// Circle c1 = Circle(9, 8, 5, 1);
	// Circle c2 = Circle(2, 8, 2, 1);
	// cerr << c1.intercept(c2) << '\n';
	// return 0;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < n; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		v.emplace_back(x, y, r, i + 1);
	}
	sort(v.begin(), v.end());
	for (auto vv : v) {
		if (parent[vv.i] == vv.i) {
			for (auto vvv : v) {
				if (parent[vvv.i] != vvv.i) {
					continue;
				}
				if (vv.intercept(vvv)) {
					parent[vvv.i] = vv.i;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << parent[i] << ' ';
	}
	cout << '\n';
	return 0;
}

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