This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<algorithm>
#define N_ 301000
using namespace std;
struct Circle {
int x, y, r, num;
bool operator<(const Circle &p)const {
return r != p.r ? r > p.r:num < p.num;
}
}w[N_];
int n, Res[N_], INF = 1e9, U[22][1<<21], UF[N_*4][22];
struct point {
int x, y, num;
bool operator<(const point &p)const {
return x != p.x ? x < p.x : y < p.y;
}
}P[N_*4];
bool Intersect(int a, int b) {
long long dx = w[a].x - w[b].x, dy = w[a].y - w[b].y, dr = w[a].r + w[b].r;
if (dx*dx + dy*dy <= dr*dr)return true;
return false;
}
void Chk(int a, int b) {
if (Res[w[b].num])return;
if (Intersect(a, b))Res[w[b].num] = w[a].num;
}
int Find(int a, int pv) {
if (a == UF[a][pv])return a;
return UF[a][pv] = Find(UF[a][pv], pv);
}
void Del(int a, int pv) {
UF[a][pv] = Find(UF[a + 1][pv], pv);
}
void Do2(int a, int nd, int pv) {
int bb;
int y1 = w[a].y - w[a].r, y2 = w[a].y + w[a].r;
if (pv >= 3) {
int b = (nd << pv), e = ((nd + 1) << pv) - 1;
bb = e + 1;
int mid;
while (b <= e) {
mid = (b + e) >> 1;
if (P[U[pv][mid]].y >= y1) {
bb = mid;
e = mid - 1;
}
else b = mid + 1;
}
}
else {
bb = (nd << pv);
}
int e = ((nd + 1) << pv);
while (1) {
bb = Find(bb, pv);
if (bb >= e)break;
int t = U[pv][bb];
if (P[t].y > y2)break;
int tt = P[t].num;
Chk(a, tt);
if (Res[w[tt].num])Del(bb, pv);
bb++;
}
}
void Do(int a, int b, int e) {
int pv = 0;
while (b <= e) {
if (b & 1) {
Do2(a, b, pv);
}
if (!(e & 1)) {
Do2(a, e, pv);
}
b = (b + 1) >> 1;
e = (e - 1) >> 1;
pv++;
}
}
void Go(int a, int bx, int ex, int by, int ey) {
point tp = { bx,-INF * 2 - 1, -1 };
int b = lower_bound(P + 1, P + n * 4 + 1, tp) - P;
tp = { ex + 1, -INF * 2 - 1, -1 };
int e = lower_bound(P + 1, P + n * 4 + 1, tp) - P - 1;
Do(a, b - 1, e - 1);
}
int main() {
int i, j;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r);
w[i].num = i;
}
sort(w + 1, w + n + 1);
for (i = 1; i <= n; i++) {
P[i] = { w[i].x - w[i].r,w[i].y - w[i].r,i };
P[i+n] = { w[i].x - w[i].r,w[i].y + w[i].r,i };
P[i+n+n] = { w[i].x + w[i].r,w[i].y - w[i].r,i };
P[i+n+n+n] = { w[i].x + w[i].r,w[i].y + w[i].r,i };
}
sort(P + 1, P + n*4 + 1);
for (i = 0; i < n * 4; i++) {
U[0][i] = i + 1;
}
for (i = 0; i < 20; i++) {
for (j = 0; j < n * 4; j += (1 << (i + 1))) {
int mid = j + (1 << i), ed = j + (1 << (i + 1));
int p1 = j, p2 = mid, pv = j;
while (p1 < mid || p2 < ed) {
if (p2 == ed || (p1 != mid && P[U[i][p1]].y < P[U[i][p2]].y)) {
U[i + 1][pv++] = U[i][p1++];
}
else {
U[i + 1][pv++] = U[i][p2++];
}
}
}
}
for (i = 0; i <= n * 4 + 10; i++) {
for (j = 0; j <= 20; j++)UF[i][j] = i;
}
for (i = 1; i <= n; i++) {
if (Res[w[i].num])continue;
Res[w[i].num] = w[i].num;
Go(i, w[i].x - w[i].r, w[i].x + w[i].r, w[i].y - w[i].r, w[i].y + w[i].r);
}
for (i = 1; i <= n; i++)printf("%d ", Res[i]);
}
Compilation message (stderr)
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
circle_selection.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |