#pragma warning(disable:4996)
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
int n;
vector<vector<ll>> circle;
vector<pair<ll, int>> sortRadius;
//set<pair<ll,int>> sortX, sortY;
//int skipX[300100], skipY[300100];
//int xIdx[300100], yIdx[300100];
set<vector<ll>> circleSet;
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;
}
map<pair<ll, ll>, multiset<vector<ll>>> SetGrid(ll gridSize)
{
map<pair<ll, ll>, multiset<vector<ll>>> myGrid;
ll x, y, r, i;
for (auto c = circleSet.begin(); c != circleSet.end(); c++)
{
x = (*c)[0], y = (*c)[1], r = (*c)[2], i = (*c)[3];
if (myGrid.insert({ {x / gridSize, y / gridSize},{{x,y,r,i}} }).second == false)
{
auto iter = myGrid.find({ x / gridSize, y / gridSize });
(*iter).second.insert({ x,y,r,i });
}
}
return myGrid;
}
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;
//좌표는 양수로만 그래야 그리드계산 편함
x += 1000000000L;
y += 1000000000L;
//1000000000
circle.push_back({ x,y,r });
circleSet.insert({ x,y,r,i });
sortRadius.push_back({ r,i });
}
sort(sortRadius.begin(), sortRadius.end(), compSort);
//sort(sortX.begin(), sortX.end());
//sort(sortY.begin(), sortY.end());
int cur, curcmp;
//int xMin, xMax, yMin, yMax;
ll rr;
fill(ans, ans + n + 2, -1);
ll gridSize = sortRadius[0].first;
map<pair<ll, ll>, multiset<vector<ll>>> gridAll = SetGrid(gridSize);
ll gridX, gridY;
ll nx, ny, nr;
int ni;
multiset<vector<ll>> curGrids;
for (int curDelete = 0; curDelete < n; curDelete++)
{
cur = sortRadius[curDelete].second;
if (ans[cur] != -1)
continue;
if (gridSize / 2 >= sortRadius[curDelete].first && gridSize>2)
{
gridSize /= 2;
gridAll = SetGrid(gridSize);
}
ans[cur] = cur;
x = circle[cur][0], y = circle[cur][1], r = circle[cur][2];
gridX = x / gridSize, gridY = y / gridSize;
circleSet.erase({ x,y,r,cur });
(*gridAll.find({ gridX,gridY })).second.erase({ x,y,r,cur });
for (int curGridX = gridX - 1; curGridX <= gridX + 1; curGridX++)
{
for (int curGridY = gridY - 1; curGridY <= gridY + 1; curGridY++)
{
auto ggg = gridAll.find({ curGridX, curGridY });
if (ggg == gridAll.end())
continue;
curGrids = (*ggg).second;
vector<multiset<vector<ll>>::iterator> eraseItems;
for (auto curCircle = curGrids.begin(); curCircle != curGrids.end(); curCircle++)
{
nx = (*curCircle)[0], ny = (*curCircle)[1], nr = (*curCircle)[2], ni = (*curCircle)[3];
if (ans[ni] != -1)
continue;
if (GetDist(x, y, nx, ny) <= (r + nr) * (r + nr))
{
ans[ni] = cur ;
eraseItems.push_back(curCircle);
circleSet.erase({ nx,ny,nr,ni });
}
}
for (auto eraseIt : eraseItems)
curGrids.erase(eraseIt);
}
}
}
for (int i = 0; i < n; i++)
printf("%d ", ans[i] + 1);
return 0;
}
Compilation message
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:74:17: warning: unused variable 'r2' [-Wunused-variable]
74 | ll x, y, r, r2;
| ^~
circle_selection.cpp:75:9: warning: unused variable 'i' [-Wunused-variable]
75 | int i;
| ^
circle_selection.cpp:96:14: warning: unused variable 'curcmp' [-Wunused-variable]
96 | int cur, curcmp;
| ^~~~~~
circle_selection.cpp:98:8: warning: unused variable 'rr' [-Wunused-variable]
98 | ll rr;
| ^~
circle_selection.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
circle_selection.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%lld %lld %lld", &x, &y, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
874 ms |
109412 KB |
Output is correct |
| 2 |
Incorrect |
864 ms |
97524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1703 ms |
123168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
