제출 #106712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106712		chemistrae03	원 고르기 (APIO18_circle_selection)	C++17	7 / 100	3031 ms	7776 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

struct Circle {
	long long x, y, r;
	int i;
	Circle(long long _x, long long _y, long long _r, int _i) : x(_x), y(_y), r(_r), i(_i) {
		// do nothing
	}
	bool intercept(const Circle &c) {
		long long dx = c.x - x, dy = c.y - y, dr = c.r + r;
		// cerr << dx << ' ' << dy << ' ' << dr << '\n';
		if (dx * dx * 1LL + dy * dy * 1LL <= dr * dr * 1LL) {
			return true;
		} else {
			return false;
		}
	}
	bool operator < (const Circle &c) { 
		return r == c.r ? i < c.i : 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 * 1LL, y * 1LL, r * 1LL, i + 1);
	}
	sort(v.begin(), v.end());
	// for (auto vv : v) {
	// 	cerr << vv.i << '\n';
	// }
	// return 0;
	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: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13