This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma warning(disable:4996)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
vector<vector<ll>> circle;
vector<pair<ll, int>> sortRadius, sortX, sortY;
int skipX[300100], skipY[300100];
int xIdx[300100], yIdx[300100];
int ans[301000];
inline ll GetDist(ll x1, ll y1, ll x2, ll y2)
{
// 아 좌표값 마이너스도 들어오네
ll xx = max(x1, x2) - min(x1, x2);
ll yy = max(y1, y2) - min(y1, y2);
return (xx * xx) + (yy * yy);
}
bool comp(const pair<ll, int>& a, const pair<ll, int>& b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
bool compSort(const pair<ll, int>& a, const pair<ll, int>& b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first > b.first;
}
int main()
{
ll x, y, r, r2;
int i;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%lld %lld %lld", &x, &y, &r);
//x = 1, y = 1, r = 3;
circle.push_back({ x,y,r });
sortRadius.push_back({ r,i });
sortX.push_back({ x,i });
sortY.push_back({ y,i });
skipX[i] = i + 1;
skipY[i] = i + 1;
}
sort(sortRadius.begin(), sortRadius.end(), compSort);
sort(sortX.begin(), sortX.end());
sort(sortY.begin(), sortY.end());
for (int i = 0; i < n; i++)
{
xIdx[sortX[i].second] = i;
yIdx[sortY[i].second] = i;
}
int cur, curcmp;
int xMin, xMax, yMin, yMax;
int next;
ll rr;
fill(ans, ans + n + 2, -1);
for (int curDelete = 0; curDelete < n; curDelete++)
{
cur = sortRadius[curDelete].second;
if (ans[cur] != -1)
continue;
x = circle[cur][0], y = circle[cur][1], r = circle[cur][2];
if (curDelete < n - 1)
r2 = r + sortRadius[curDelete + 1].first + 1;
else
r2 = r * 2 + 1;
// a이하를 찾아야하는데 lower bound는 a이상인걸 찾으니까.. 근데 그 이하인걸 찾아야하니 1빼줌
xMin = lower_bound(sortX.begin(), sortX.end(), pair<ll, int>(x - r2, -1), comp) - sortX.begin();
xMax = upper_bound(sortX.begin(), sortX.end(), pair<ll, int>(x + r2, 301000), comp) - sortX.begin();
yMin = lower_bound(sortY.begin(), sortY.end(), pair<ll, int>(y - r2, -1), comp) - sortY.begin();
yMax = upper_bound(sortY.begin(), sortY.end(), pair<ll, int>(y + r2, 301000), comp) - sortY.begin();
xMin--;
yMin--;
if (xMin < 0) xMin = 0;
if (yMin < 0) yMin = 0;
if (xMin >= sortX.size()) xMin = sortX.size() - 1;
if (yMin >= sortY.size()) yMin = sortY.size() - 1;
if (xMax >= sortX.size()) xMax = sortX.size() - 1;
if (yMax >= sortY.size()) yMax = sortY.size() - 1;
//xMin = 0, yMin = 0, xMax = n - 1, yMax = n - 1;
ans[cur] = cur;
if (xIdx[cur] - 1 >= 0)
{
skipX[xIdx[cur] - 1] = skipX[xIdx[cur]];
if (skipX[xIdx[cur] - 1] == 0) skipX[xIdx[cur] - 1] = n + 1;
}
if (yIdx[cur] - 1 >= 0)
{
skipY[yIdx[cur] - 1] = skipY[yIdx[cur]];
if (skipY[yIdx[cur] - 1] == 0) skipY[yIdx[cur] - 1] = n + 1;
}
//xIdx[cur]
if (xMax - xMin < yMax - yMin)
{
i = xMin;
while (i <= xMax)
{
curcmp = sortX[i].second;
next = skipX[i];
if (ans[curcmp] != -1)
{
i = next;
continue;
}
rr = r + circle[curcmp][2];
if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
{
ans[curcmp] = cur;
//sortX.erase(sortX.begin() + i);
if (i - 1 >= 0)
skipX[i - 1] = skipX[i];
if (yIdx[curcmp] - 1 >= 0)
{
skipY[yIdx[curcmp] - 1] = skipY[yIdx[curcmp]];
if (skipY[yIdx[curcmp] - 1] == 0) skipY[yIdx[curcmp] - 1] = n + 1;
}
}
i = next;
}
}
else
{
i = yMin;
while (i <= yMax)
{
curcmp = sortY[i].second;
next = skipY[i];
if (ans[curcmp] != -1)
{
i = next;
continue;
}
rr = r + circle[curcmp][2];
if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
{
ans[curcmp] = cur;
//sortX.erase(sortX.begin() + i);
if (i - 1>= 0)
skipY[i - 1] = skipY[i];
if (xIdx[curcmp] - 1 >= 0)
{
skipX[xIdx[curcmp] - 1] = skipX[xIdx[curcmp]];
if (skipX[xIdx[curcmp] - 1] == 0) skipX[xIdx[curcmp] - 1] = n + 1;
}
}
i = next;
}
/*
for (int i = yMax; i >= yMin; i--)
{
curcmp = sortY[i].second;
if (ans[curcmp]!= -1) continue;
rr = r + circle[curcmp][2];
if (GetDist(x, y, circle[curcmp][0], circle[curcmp][1]) <= rr * rr)
{
ans[curcmp] = cur;
//sortY.erase(sortY.begin() + i);
}
}*/
}
}
for (int i = 0; i < n; i++)
printf("%d ", ans[i] + 1);
return 0;
}
Compilation message (stderr)
circle_selection.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
1 | #pragma warning(disable:4996)
|
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | if (xMin >= sortX.size()) xMin = sortX.size() - 1;
| ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if (yMin >= sortY.size()) yMin = sortY.size() - 1;
| ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | if (xMax >= sortX.size()) xMax = sortX.size() - 1;
| ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | if (yMax >= sortY.size()) yMax = sortY.size() - 1;
| ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
circle_selection.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%lld %lld %lld", &x, &y, &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... |