# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90971 | tincamatei | Circle selection (APIO18_circle_selection) | C++14 | 3036 ms | 54224 KiB |
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 <bits/stdc++.h>
using namespace std;
const int MAX_N = 300000;
int xc[1+MAX_N], yc[1+MAX_N], rc[1+MAX_N];
int poz[1+MAX_N], rez[1+MAX_N];
long long ld[1+MAX_N], rd[1+MAX_N];
set<pair<long long, int>> sl, sr;
bool cmp(int a, int b) {
return rc[a] > rc[b] || (rc[a] == rc[b] && a < b);
}
double dist(int xa, int ya, int xb, int yb) {
return sqrt((long long)(xa - xb) * (xa - xb) +
(long long)(ya - yb) * (ya - yb));
}
int main() {
#ifdef HOME
FILE *fin = fopen("input.in", "r");
FILE *fout = fopen("output.out", "w");
#else
FILE *fin = stdin;
FILE *fout = stdout;
#endif
int n, ox, oy, mnx, mny;
mnx = mny = 1000000000;
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; ++i) {
fscanf(fin, "%d%d%d", &xc[i], &yc[i], &rc[i]);
mnx = min(mnx, xc[i]);
mny = min(mny, yc[i]);
}
ox = oy = -2000000000;
for(int i = 1; i <= n; ++i) {
xc[i] -= mnx;
yc[i] -= mny;
long long d = llabs(ox - xc[i]) + llabs(oy - yc[i]);
ld[i] = d - 2 * rc[i];
rd[i] = d + 2 * rc[i];
sl.insert(make_pair(ld[i], i));
sr.insert(make_pair(rd[i], i));
poz[i - 1] = i;
}
sort(poz, poz + n, cmp);
for(int i = 0; i < n; ++i) {
int x = poz[i];
if(rez[x] == 0) {
set<pair<long long, int> >::iterator it;
it = sl.lower_bound(make_pair(ld[x], -1));
while(it != sl.end() && it->first <= rd[x]) {
int todel = it->second;
if((long long)(rc[x] + rc[todel]) * (rc[x] + rc[todel]) >=
(long long)(xc[x] - xc[todel]) * (xc[x] - xc[todel]) +
(long long)(yc[x] - yc[todel]) * (yc[x] - yc[todel])) {
rez[todel] = x;
sr.erase(make_pair(rd[todel], todel));
it = sl.erase(it);
} else
it++;
}
it = sr.lower_bound(make_pair(ld[x], -1));
while(it != sr.end() && it->first <= rd[x]) {
int todel = it->second;
if((long long)(rc[x] + rc[todel]) * (rc[x] + rc[todel]) >=
(long long)(xc[x] - xc[todel]) * (xc[x] - xc[todel]) +
(long long)(yc[x] - yc[todel]) * (yc[x] - yc[todel])) {
rez[todel] = x;
sl.erase(make_pair(ld[todel], todel));
it = sr.erase(it);
} else
it++;
}
}
}
for(int i = 1; i <= n; ++i)
fprintf(fout, "%d ", rez[i]);
#ifdef HOME
fclose(fin);
fclose(fout);
#endif
return 0;
}
Compilation message (stderr)
# | 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... |