Submission #611075

#	Time	Username	Problem	Language	Result	Execution time	Memory
611075		GusterGoose27	Circle selection (APIO18_circle_selection)	C++11	100 / 100	2734 ms	59884 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

class Circle {
public:
	int x;
	int y;
	int r;
	int id;
	bool active = 1;
	Circle() {}
	Circle(int xn, int yn, int rn, int i) {
		x = xn;
		y = yn;
		r = rn;
		id = i;
	}
};

bool operator<(Circle &a, Circle &b) {
	return (a.r == b.r) ? (a.id < b.id) : (a.r > b.r);
}

bool intersect(Circle &a, Circle &b) {
	ll xdiff = a.x-b.x;
	ll ydiff = a.y-b.y;
	ll rsum = a.r+b.r;
	return rsum*rsum >= xdiff*xdiff+ydiff*ydiff;
}

const int MAXN = 3e5;
int n;
Circle circles[MAXN];
map<pii, set<int>> grid_div;
int par[MAXN];
int sq_sz;

void make_div() {
	grid_div.clear();
	for (int i = 0; i < n; i++) {
		if (!circles[i].active) continue;
		grid_div[pii(circles[i].x/sq_sz, circles[i].y/sq_sz)].insert(i);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		circles[i] = Circle(x, y, r, i);
	}
	sort(circles, circles+n);
	sq_sz = circles[0].r;
	make_div();
	for (int i = 0; i < n; i++) {
		if (!circles[i].active) continue;
		if (circles[i].r <= sq_sz/2) {
			sq_sz = circles[i].r;
			make_div();
		}
		int sqx = circles[i].x/sq_sz;
		int sqy = circles[i].y/sq_sz;
		for (int x_diff = -2; x_diff <= 2; x_diff++) {
			for (int y_diff = -2; y_diff <= 2; y_diff++) {
				pii cur = pii(sqx+x_diff, sqy+y_diff);
				if (grid_div.find(cur) != grid_div.end()) {
					vector<int> r;
					for (int circ: grid_div[cur]) {
						if (intersect(circles[circ], circles[i])) {
							par[circles[circ].id] = circles[i].id;
							r.push_back(circ);
							circles[circ].active = 0;
						}
					}
					for (int circ: r) grid_div[cur].erase(circ);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (i) cout << ' ';
		cout << (1+par[i]);
	}
	cout << "\n";
}

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