Submission #1174229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174229		madamadam3	Circle selection (APIO18_circle_selection)	C++20	0 / 100	227 ms	19164 KiB

circle_selection

#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);

        if (dist <= 4 * radius * radius) {
            removed[nearest->id] = i;
            tree.remove(nearest->x, nearest->y);
        }
    }

    for (int i = 0; i < n; i++) {
        cout << removed[i] + 1 << " ";
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13