#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
struct Circle
{
int64_t x;
int64_t y;
int64_t r;
int64_t i;
int64_t elimBy;
int64_t minX() const { return x - r; }
int64_t maxX() const { return x + r; }
int64_t minY() const { return y - r; }
int64_t maxY() const { return y + r; }
bool intersects(const Circle& other) const
{
int64_t dx = x - other.x;
int64_t dy = y - other.y;
int64_t rSum = r + other.r;
return dx * dx + dy * dy <= rSum * rSum;
}
};
Circle* outerCircle;
struct OctNode
{
int64_t minX;
int64_t minY;
int64_t maxX;
int64_t maxY;
std::vector<Circle*> circles;
OctNode* children = nullptr;
bool intersects(int64_t x, int64_t y, int64_t r)
{
return !(x - r >= maxX || x + r <= minX || y - r >= maxY || y + r <= minY);
}
bool contains(int64_t x, int64_t y, int64_t r)
{
return x - r >= minX && x + r < maxX && y - r >= minY && y + r < maxY;
}
void mark()
{
if (children)
{
for (int i = 0; i < 4; i++)
{
if (children[i].intersects(outerCircle->x, outerCircle->y, outerCircle->r))
children[i].mark();
}
}
for (Circle* c : circles)
{
if (c->elimBy == -1 && c->intersects(*outerCircle))
{
c->elimBy = outerCircle->i;
}
}
}
};
void genOctree(OctNode* node)
{
int64_t halfSX = (node->maxX - node->minX) / 2;
int64_t halfSY = (node->maxY - node->minY) / 2;
int64_t midX = node->minX + halfSX;
int64_t midY = node->minY + halfSY;
bool subdivide = false;
for (Circle* circle : node->circles)
{
if (circle->maxX() < midX || circle->minX() > midX || circle->maxY() > midY || circle->minY() < midY)
{
subdivide = true;
break;
}
}
if (!subdivide)
return;
node->children = new OctNode[4];
for (int i = 0; i < 4; i++)
{
node->children[i].minX = (i % 2) ? midX : node->minX;
node->children[i].maxX = (i % 2) ? node->maxX : midX;
node->children[i].minY = (i / 2) ? midY : node->minY;
node->children[i].maxY = (i / 2) ? node->maxY : midY;
for (int j = node->circles.size(); j >= 0; j--)
{
if (node->contains(node->circles[j]->x, node->circles[j]->y, node->circles[j]->r))
{
node->children[j].circles.push_back(node->circles[j]);
node->circles[j] = node->circles.back();
node->circles.pop_back();
}
}
}
}
int main()
{
int num;
std::cin >> num;
std::vector<Circle> circles(num);
std::vector<Circle*> cByMin(num);
std::vector<Circle*> cByMax(num);
bool allZeroY = true;
int64_t sameRad = -1;
for (int i = 0; i < num; i++)
{
std::cin >> circles[i].x;
std::cin >> circles[i].y;
std::cin >> circles[i].r;
circles[i].i = i;
circles[i].elimBy = -1;
cByMin[i] = &circles[i];
cByMax[i] = &circles[i];
if (i == 0)
sameRad = circles[i].r;
else if (sameRad != circles[i].r)
sameRad = -1;
if (circles[i].y != 0)
allZeroY = false;
}
if (sameRad == -1)
{
std::sort(ALL(circles), [&] (const Circle& a, const Circle& b)
{
if (a.r == b.r)
return a.i < b.i;
return a.r > b.r;
});
}
if (allZeroY)
{
std::sort(ALL(cByMin), [&] (const Circle* a, const Circle* b)
{
return a->minX() < b->minX();
});
std::sort(ALL(cByMax), [&] (const Circle* a, const Circle* b)
{
return a->maxX() < b->maxX();
});
for (Circle& outer : circles)
{
if (outer.elimBy != -1)
continue;
outer.elimBy = outer.i;
auto minB = std::lower_bound(ALL(cByMin), outer.minX(), [&] (Circle* c, int64_t pos) { return c->minX() < pos; });
auto minE = std::upper_bound(ALL(cByMin), outer.maxX(), [&] (int64_t pos, Circle* c) { return pos < c->minX(); });
auto maxB = std::lower_bound(ALL(cByMax), outer.minX(), [&] (Circle* c, int64_t pos) { return c->maxX() < pos; });
auto maxE = std::upper_bound(ALL(cByMax), outer.maxX(), [&] (int64_t pos, Circle* c) { return pos <= c->maxX(); });
std::for_each(minB, minE, [&] (Circle* c)
{
if (c->elimBy == -1)
c->elimBy = outer.i;
});
std::for_each(maxB, maxE, [&] (Circle* c)
{
if (c->elimBy == -1)
c->elimBy = outer.i;
});
}
}
else if (num <= 5000)
{
for (Circle& outer : circles)
{
if (outer.elimBy != -1)
continue;
outer.elimBy = outer.i;
for (Circle& inner : circles)
{
if (inner.elimBy == -1 && inner.intersects(outer))
inner.elimBy = outer.i;
}
}
}
else
{
int64_t minX;
int64_t minY;
int64_t maxX;
int64_t maxY;
OctNode root;
root.children = circles;
root.minX = INT64_MAX;
root.minY = INT64_MAX;
root.maxX = INT64_MIN;
root.maxY = INT64_MIN;
for (const Circle& circle : circles)
{
root.minX = std::min(root.minX, circle.minX());
root.maxX = std::min(root.maxX, circle.maxX());
root.minY = std::min(root.minY, circle.minY());
root.maxY = std::min(root.maxY, circle.maxY());
}
root.maxX++;
root.maxY++;
genOctree(&root);
for (Circle& circle : circles)
{
if (circle.elimBy == -1)
{
circle.elimBy = circle.i;
outerCircle = &circle;
root.mark();
}
}
}
std::vector<int64_t> result(num);
for (int i = 0; i < num; i++)
result[circles[i].i] = circles[i].elimBy + 1;
for (int i = 0; i < num; i++)
std::cout << result[i] << " ";
std::cout << std::endl;
}
Compilation message
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:206:19: error: cannot convert 'std::vector<Circle>' to 'OctNode*' in assignment
root.children = circles;
^~~~~~~
circle_selection.cpp:200:11: warning: unused variable 'minX' [-Wunused-variable]
int64_t minX;
^~~~
circle_selection.cpp:201:11: warning: unused variable 'minY' [-Wunused-variable]
int64_t minY;
^~~~
circle_selection.cpp:202:11: warning: unused variable 'maxX' [-Wunused-variable]
int64_t maxX;
^~~~
circle_selection.cpp:203:11: warning: unused variable 'maxY' [-Wunused-variable]
int64_t maxY;
^~~~
