#include <bits/stdc++.h>
using namespace std;
int euclidean_distance(int x1, int y1, int x2, int y2) {
int dx = x2 - x1;
int dy = y2 - y1;
return dx * dx + dy * dy;
}
struct Node {
int x, y, id;
Node *left, *right;
Node(int _x, int _y, int _id) : x(_x), y(_y), id(_id), left(nullptr), right(nullptr) {}
};
class KDTree {
Node* root;
// Insert helper
Node* insert_into(Node* node, int nx, int ny, int depth, int id) {
if (!node) {
return new Node(nx, ny, id);
}
int dimension = depth % 2;
if ((dimension == 0 && nx < node->x) || (dimension == 1 && ny < node->y))
node->left = insert_into(node->left, nx, ny, depth + 1, id);
else
node->right = insert_into(node->right, nx, ny, depth + 1, id);
return node;
}
// Finds the node with minimum value along dimension d in subtree rooted at node.
Node* findMin(Node* node, int d, int depth) {
if (!node) return nullptr;
int cd = depth % 2;
if (cd == d) {
// Only left subtree could contain a smaller value in this dimension.
if (node->left == nullptr)
return node;
return findMin(node->left, d, depth + 1);
} else {
// Check both subtrees.
Node* leftMin = findMin(node->left, d, depth + 1);
Node* rightMin = findMin(node->right, d, depth + 1);
Node* minNode = node;
if (leftMin && (d == 0 ? leftMin->x < minNode->x : leftMin->y < minNode->y))
minNode = leftMin;
if (rightMin && (d == 0 ? rightMin->x < minNode->x : rightMin->y < minNode->y))
minNode = rightMin;
return minNode;
}
}
// Delete helper. Returns the new subtree after deletion.
Node* delete_node(Node* node, int x, int y, int depth) {
if (!node) return nullptr;
int cd = depth % 2;
// Check if we found the node
if (node->x == x && node->y == y) {
// If node has a right child, find min in right subtree in current dimension.
if (node->right) {
Node* minNode = findMin(node->right, cd, depth + 1);
node->x = minNode->x;
node->y = minNode->y;
node->right = delete_node(node->right, minNode->x, minNode->y, depth + 1);
}
// If no right child but left child exists, find min in left subtree and then move left subtree up.
else if (node->left) {
Node* minNode = findMin(node->left, cd, depth + 1);
node->x = minNode->x;
node->y = minNode->y;
// After replacing, we need to remove the duplicate from the left subtree.
node->right = delete_node(node->left, minNode->x, minNode->y, depth + 1);
node->left = nullptr;
} else {
// Leaf node
delete node;
return nullptr;
}
return node;
}
// If not found, traverse subtree based on splitting dimension.
if ((cd == 0 && x < node->x) || (cd == 1 && y < node->y))
node->left = delete_node(node->left, x, y, depth + 1);
else
node->right = delete_node(node->right, x, y, depth + 1);
return node;
}
void find_nearest(Node* node, int qx, int qy, int depth, int &best_distance, Node* best_node) {
if (!node) return;
int dist_to = euclidean_distance(qx, qy, node->x, node->y);
if (dist_to < best_distance) {
best_distance = dist_to;
best_node = node;
}
int dimension = depth % 2;
Node *first = node->left, *second = node->right;
if ((dimension == 0 && qx > node->x) || (dimension == 1 && qy > node->y)) {
first = node->right;
second = node->left;
}
find_nearest(first, qx, qy, depth + 1, best_distance, best_node);
int dc = dimension == 0 ? node->x - qx : node->y - qy;
if (dc * dc < best_distance) {
find_nearest(second, qx, qy, depth + 1, best_distance, best_node);
}
}
public:
KDTree() : root(nullptr) {}
// Public insert method.
void insert(int x, int y, int id) {
root = insert_into(root, x, y, 0, id);
}
// Public deletion method.
void remove(int x, int y) {
root = delete_node(root, x, y, 0);
}
// Return the squared distance to the closest point.
Node* closest(int x, int y) {
int best_distance = INT_MAX;
Node* best_node = nullptr;
find_nearest(root, x, y, 0, best_distance, best_node);
return best_node;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
KDTree tree;
int n; cin >> n;
vector<int> x(n), y(n), r(n);
vector<int> removed(n, -1);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> r[i];
tree.insert(x[i], y[i], i);
}
int radius = r[0];
for (int i = 0; i < n; i++) {
if (removed[i] != -1) continue;
removed[i] = i;
Node *nearest = tree.closest(x[i], y[i]);
int dist = euclidean_distance(x[i], y[i], nearest->x, nearest->y);
while (dist <= 4 * radius * radius) {
removed[nearest->id] = i;
tree.remove(nearest->x, nearest->y);
nearest = tree.closest(x[i], y[i]);
dist = euclidean_distance(x[i], y[i], nearest->x, nearest->y);
}
}
for (int i = 0; i < n; i++) {
cout << removed[i] + 1 << " ";
}
return 0;
}
