Submission #243925

#	Time	Username	Problem	Language	Result	Execution time	Memory
243925		atoiz	Circle selection (APIO18_circle_selection)	C++14	75 / 100	999 ms	40184 KiB

circle_selection

// https://oj.uz/submission/77965

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const double INF = 1e9, EPS = 1e-8;

double sqr(double x) { return x * x; }
void minimize(double &x, double y) { x = (x < y ? x : y); }
void maximize(double &x, double y) { x = (x > y ? x : y); }

struct Box
{
	double x0, x1, y0, y1;
	Box(double _x0 = INF, double _x1 = -INF, double _y0 = INF, double _y1 = -INF): x0(_x0), x1(_x1), y0(_y0), y1(_y1) {}
	bool intersect(const Box &b) const { return (x0 < b.x1 + EPS && b.x0 < x1 + EPS && y0 < b.y1 + EPS && b.y0 < y1 + EPS); }
	void expand(const Box &b) { minimize(x0, b.x0), minimize(y0, b.y0), maximize(x1, b.x1), maximize(y1, b.y1); }
};

struct Circle
{
	double x, y, r;
	int i;
	bool intersect(const Circle &c) const { return sqr(c.x - x) + sqr(c.y - y) < sqr(r + c.r) + EPS; }
	Box toBox() { return Box(x - r, x + r, y - r, y + r); }
};

bool compX(const Circle &a, const Circle &b) { return (abs(a.x - b.x) < EPS ? (a.y < b.y) : (a.x < b.x)); }
bool compY(const Circle &a, const Circle &b) { return (abs(a.y - b.y) < EPS ? (a.x < b.x) : (a.y < b.y)); }
bool compR(const Circle &a, const Circle &b) { return (abs(a.r - b.r) < EPS ? (a.i < b.i) : (a.r > b.r)); }

int n;
vector<int> ans;
vector<Circle> circles, cirTree;
vector<Box> boxTree;

void build(int lo = 0, int hi = n - 1, bool byX = 0)
{
	int mid = (lo + hi) >> 1;
	nth_element(cirTree.begin() + lo, cirTree.begin() + mid, cirTree.begin() + hi + 1, (byX ? compX : compY));
	boxTree[mid] = cirTree[mid].toBox();

	if (lo < mid) {
		build(lo, mid - 1, !byX);
		boxTree[mid].expand(boxTree[(lo + mid - 1) >> 1]);
	}

	if (mid < hi) {
		build(mid + 1, hi, !byX);
		boxTree[mid].expand(boxTree[(mid + 1 + hi) >> 1]);
	}

	// cout << mid << ' ' << lo << ' ' << hi << ' ' << cirTree[mid].i << ": ";
	// cout << boxTree[mid].x0 << ' ' << boxTree[mid].x1 << ' ' << boxTree[mid].y0 << ' ' << boxTree[mid].y1 << endl;
}

void get(Circle &c, Box &b, int lo = 0, int hi = n - 1, bool byX = 0)
{
	int mid = (lo + hi) >> 1;
	if (ans[cirTree[mid].i] == -1 && cirTree[mid].intersect(c)) ans[cirTree[mid].i] = c.i;
	// cout << c.i << ": " << lo << ' ' << hi << ' ' << cirTree[mid].i << " - ";
	// cout << boxTree[mid].x0 << ' ' << boxTree[mid].x1 << ' ' << boxTree[mid].y0 << ' ' << boxTree[mid].y1 << endl;

	boxTree[mid] = Box(INF, -INF, INF, -INF);
	if (ans[cirTree[mid].i] == -1) boxTree[mid] = cirTree[mid].toBox();
	int lc = (lo + mid - 1) >> 1, rc = (mid + 1 + hi) >> 1;
	if (lo < mid) {
		if (boxTree[lc].intersect(b)) get(c, b, lo, mid - 1, !byX);
		boxTree[mid].expand(boxTree[lc]);
	}
	if (mid < hi) {
		if (boxTree[rc].intersect(b)) get(c, b, mid + 1, hi, !byX);
		boxTree[mid].expand(boxTree[rc]);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	circles.resize(n);
	for (int i = 0; i < n; ++i) {
		cin >> circles[i].x >> circles[i].y >> circles[i].r;
		circles[i].i = i;
	}
	sort(circles.begin(), circles.end(), compR);

	cirTree = circles;
	boxTree.resize(n);
	ans.assign(n, -1);
	build();

	for (auto &c : circles) if (ans[c.i] == -1) {
		ans[c.i] = c.i;
		Box b = c.toBox();
		get(c, b);
	}
	for (int i = 0; i < n; ++i) cout << ans[i] + 1 << ' ';
}

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