#1083868 (C++17) No.2436 Min Diff Distance

• 問題: No.2436 Min Diff Distance
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:06:27
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 273 ms / 2,000 ms
• コード長: 9,332 bytes
• コンパイル時間: 1,205 ms
• コンパイル使用メモリ: 107,124 KB
• 実行使用メモリ: 31,420 KB
• 最終ジャッジ日時: 2025-05-14 13:07:41
• 合計ジャッジ時間: 6,296 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	AC * 23

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <numeric> // Required for std::iota

// Define long long for large coordinates and distances
using ll = long long;

// Structure to represent a point in original (X, Y) and transformed (U, V) coordinates.
// U = X + Y, V = X - Y. Manhattan distance in (X, Y) is Chebyshev distance in (U, V).
// Also store its original index for identification.
struct Point {
    ll x, y, u, v;
    int id; // Original index 0 to N-1
};

// Structure for K-D tree node
struct KDNode {
    Point point; // Stores the actual point data for the node
    KDNode *left = nullptr;
    KDNode *right = nullptr;
    int axis; // Splitting axis: 0 for U, 1 for V
};

// Global vector to store all points. Accessed by buildKDTreeIdx using indices.
std::vector<Point> global_points;

// Comparison functors used with std::nth_element to partition indices based on point coordinates.
struct CompareUIdx {
    bool operator()(int a, int b) const {
        return global_points[a].u < global_points[b].u;
    }
};

struct CompareVIdx {
     bool operator()(int a, int b) const {
        return global_points[a].v < global_points[b].v;
    }
};

// Function to build the K-D tree recursively using indices into the global_points vector.
// This approach avoids copying large Point structures and uses less memory.
// The tree nodes still store Point data for efficient access during queries.
KDNode* buildKDTreeIdx(std::vector<int>& indices, int depth) {
    // Base case: If no indices, return nullptr.
    if (indices.empty()) {
        return nullptr;
    }

    // Determine the splitting axis based on depth (alternating U and V).
    int axis = depth % 2; 

    // Find the median index within the current list of indices.
    size_t median_idx_in_indices = indices.size() / 2;
    
    // Partition the indices using nth_element. This puts the index of the median point
    // at the `median_idx_in_indices` position and ensures elements before are <= and after are >=
    // based on the coordinate value along the current axis. This runs in O(N) average time.
    if (axis == 0) { // Split on U axis
         std::nth_element(indices.begin(), indices.begin() + median_idx_in_indices, indices.end(), CompareUIdx());
    } else { // Split on V axis
         std::nth_element(indices.begin(), indices.begin() + median_idx_in_indices, indices.end(), CompareVIdx());
    }
    
    // Get the index of the median point in the global_points vector.
    int median_point_idx = indices[median_idx_in_indices];

    // Create a new K-D tree node.
    KDNode* node = new KDNode();
    // The node stores the actual Point data corresponding to the median index.
    node->point = global_points[median_point_idx]; 
    node->axis = axis;

    // Create index vectors for left and right children.
    // Indices before the median go to the left child, indices after go to the right child.
    // The median itself is stored in the current node.
    std::vector<int> left_indices(indices.begin(), indices.begin() + median_idx_in_indices);
    std::vector<int> right_indices(indices.begin() + median_idx_in_indices + 1, indices.end());

    // Recursively build the left and right subtrees.
    // Pass the newly created (copied) index vectors to the recursive calls.
    node->left = buildKDTreeIdx(left_indices, depth + 1);
    node->right = buildKDTreeIdx(right_indices, depth + 1);

    return node; // Return the newly created node.
}

// Function to calculate Chebyshev distance (L_infinity norm) between two points using their (U, V) coordinates.
ll chebyshevDist(const Point& p1, const Point& p2) {
    return std::max(std::abs(p1.u - p2.u), std::abs(p1.v - p2.v));
}

// Global variable to store the minimum distance found during a nearest neighbor query.
ll current_best_dist;

// Recursive function to query the K-D tree for the nearest neighbor of `query_point`.
// Updates `current_best_dist` globally.
void findNearest(KDNode* node, const Point& query_point) {
    // Base case: If node is null, stop recursion.
    if (node == nullptr) {
        return;
    }

    // Calculate distance from the point stored in the current node to the query point.
    // Important: Only consider this point if it's not the query point itself (check by ID).
    if (node->point.id != query_point.id) {
       ll dist = chebyshevDist(node->point, query_point);
       // Update the global minimum distance if this point is closer.
       current_best_dist = std::min(current_best_dist, dist);
    }

    // Determine which child subtree to visit first.
    // Go towards the half-space containing the query point first.
    KDNode *target_subtree, *other_subtree;
    // Get the coordinate of the query point and node point along the node's splitting axis.
    ll query_coord = (node->axis == 0) ? query_point.u : query_point.v;
    ll node_coord = (node->axis == 0) ? node->point.u : node->point.v;

    // Decide traversal order based on query point's position relative to the splitting plane.
    if (query_coord < node_coord) {
        target_subtree = node->left;
        other_subtree = node->right;
    } else {
        target_subtree = node->right;
        other_subtree = node->left;
    }

    // Recursively search the target subtree first.
    findNearest(target_subtree, query_point);

    // Pruning step: Check if the other subtree could possibly contain a closer point.
    // Calculate the distance from the query point to the splitting plane.
    ll axis_dist = std::abs(query_coord - node_coord);
    
    // If the distance along the splitting axis is already greater than or equal to the current best distance,
    // then no point in the other subtree can be closer (since Chebyshev distance is max of axis distances).
    // So, only search the other subtree if `axis_dist < current_best_dist`.
    if (axis_dist < current_best_dist) {
         findNearest(other_subtree, query_point);
    }
}

// Function to recursively delete the K-D tree nodes and free memory.
void deleteKDTree(KDNode* node) {
    if (node == nullptr) return;
    deleteKDTree(node->left);
    deleteKDTree(node->right);
    delete node;
}


int main() {
    // Faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Number of points
    std::cin >> N;
    
    // Problem constraint guarantees N >= 2.

    // Resize global points vector once to avoid reallocations.
    global_points.resize(N); 
    
    // Variables to track min/max U and V coordinates for calculating max distances.
    ll min_U = std::numeric_limits<ll>::max();
    ll max_U = std::numeric_limits<ll>::min();
    ll min_V = std::numeric_limits<ll>::max();
    ll max_V = std::numeric_limits<ll>::min();

    // Read input points and compute transformed coordinates (U, V).
    // Also find the min/max U and V values.
    for (int i = 0; i < N; ++i) {
        ll x, y;
        std::cin >> x >> y;
        global_points[i] = {x, y, x + y, x - y, i}; // Store point data with original index i
        min_U = std::min(min_U, global_points[i].u);
        max_U = std::max(max_U, global_points[i].u);
        min_V = std::min(min_V, global_points[i].v);
        max_V = std::max(max_V, global_points[i].v);
    }

    // Calculate maximum Manhattan distance M_i for each point i.
    // In (U, V) coordinates, this is the maximum Chebyshev distance to any other point.
    // This max distance is determined by the point's distance to the bounding box corners defined by min/max U and V.
    std::vector<ll> M(N);
    for (int i = 0; i < N; ++i) {
        M[i] = std::max({global_points[i].u - min_U, max_U - global_points[i].u, global_points[i].v - min_V, max_V - global_points[i].v});
    }

    // Prepare initial vector of indices [0, 1, ..., N-1].
    std::vector<int> initial_indices(N);
    std::iota(initial_indices.begin(), initial_indices.end(), 0); 

    // Build the K-D Tree using the indices. Average time complexity O(N log N).
    KDNode* root = buildKDTreeIdx(initial_indices, 0);

    // Calculate minimum Manhattan distance m_i for each point i.
    // This is equivalent to finding the nearest neighbor in (U, V) coordinates using Chebyshev distance.
    std::vector<ll> m(N);
    for (int i = 0; i < N; ++i) {
        // Reset the global best distance for each query.
        current_best_dist = std::numeric_limits<ll>::max();
        // Perform nearest neighbor search. Average time complexity O(log N).
        findNearest(root, global_points[i]);
        
        // Store the found minimum distance for point i.
        // Since N >= 2 and points are distinct, a nearest neighbor other than itself must exist.
        // `current_best_dist` will be updated unless something is fundamentally wrong.
        m[i] = current_best_dist;
    }

    // Calculate P_i = |M_i - m_i| for each point and find the minimum P_i.
    // Since M_i is max distance and m_i is min distance, M_i >= m_i, so absolute value isn't strictly needed.
    ll min_P = std::numeric_limits<ll>::max();
    for (int i = 0; i < N; ++i) {
        min_P = std::min(min_P, M[i] - m[i]);
    }

    // Output the final minimum P value.
    std::cout << min_P << std::endl;

    // Cleanup allocated memory for the K-D tree.
    deleteKDTree(root);

    return 0;
}