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

• 問題: No.2436 Min Diff Distance
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:03:13
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 329 ms / 2,000 ms
• コード長: 11,624 bytes
• コンパイル時間: 1,171 ms
• コンパイル使用メモリ: 100,448 KB
• 実行使用メモリ: 24,516 KB
• 最終ジャッジ日時: 2025-05-14 13:04:32
• 合計ジャッジ時間: 6,902 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

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

ソースコード

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

// Structure to represent a point in original and transformed coordinates
struct Point {
    long long x, y; // Original coordinates
    long long s, d; // Transformed coordinates: s = x+y, d = x-y
    int id; // Original index (0 to N-1)
};

// Calculate Chebyshev distance between two points using their transformed coordinates
// This is equivalent to the Manhattan distance between the points in original coordinates.
long long chebyshev_dist(const Point& p1, const Point& p2) {
    // The formula is max(|s1 - s2|, |d1 - d2|)
    return std::max(std::abs(p1.s - p2.s), std::abs(p1.d - p2.d));
}

// Node structure for the K-D tree
struct KDNode {
    int point_idx; // Index into the original 'points' vector
    KDNode *left = nullptr, *right = nullptr;
    // Bounding box for the subtree rooted at this node, using transformed coordinates (s, d)
    long long min_s, max_s, min_d, max_d; 
};

// Comparator for std::nth_element based on S coordinate (s = x+y) using indices
struct CompareSByIdx {
    const std::vector<Point>& points_ref;
    CompareSByIdx(const std::vector<Point>& points) : points_ref(points) {}
    bool operator()(int a_idx, int b_idx) const {
        return points_ref[a_idx].s < points_ref[b_idx].s;
    }
};

// Comparator for std::nth_element based on D coordinate (d = x-y) using indices
struct CompareDByIdx {
    const std::vector<Point>& points_ref;
    CompareDByIdx(const std::vector<Point>& points) : points_ref(points) {}
    bool operator()(int a_idx, int b_idx) const {
        return points_ref[a_idx].d < points_ref[b_idx].d;
    }
};

// Recursive function to build the K-D tree
// Operates on a range of indices [begin, end) within the 'point_indices' vector.
// Modifies the range [begin, end) in place using std::nth_element to partition points.
KDNode* build_kdtree_inplace(std::vector<int>::iterator begin, std::vector<int>::iterator end, const std::vector<Point>& all_points, int depth) {
    // Base case: If the range is empty, return nullptr.
    if (begin == end) {
        return nullptr;
    }

    // Determine the splitting axis based on the current depth (alternating S and D)
    int axis = depth % 2; // 0 for S axis, 1 for D axis
    size_t N_local = std::distance(begin, end); // Number of points in the current range
    size_t median_offset = N_local / 2; // Index of the median element within the range
    auto median_it = begin + median_offset; // Iterator to the median element

    // Partition the range of indices around the median point based on the current axis coordinate.
    // std::nth_element rearranges the elements in [begin, end) such that the element at median_it
    // is the element that would be in that position if the range were sorted. All elements before
    // median_it are less than or equal to it, and all elements after are greater than or equal to it.
    if (axis == 0) { // Partition by S coordinate
        std::nth_element(begin, median_it, end, CompareSByIdx(all_points));
    } else { // Partition by D coordinate
        std::nth_element(begin, median_it, end, CompareDByIdx(all_points));
    }

    int median_pt_idx = *median_it; // Get the index (into all_points) of the point at the median position.
    KDNode* node = new KDNode(); // Create a new node for the K-D tree.
    node->point_idx = median_pt_idx; // Store the index of the point in the node.

    // Recursively build the left and right subtrees.
    // The left child will contain points from the range [begin, median_it).
    node->left = build_kdtree_inplace(begin, median_it, all_points, depth + 1);
    // The right child will contain points from the range [median_it + 1, end).
    auto next_it = median_it; 
    ++next_it; // Iterator to the element immediately after the median.
    node->right = build_kdtree_inplace(next_it, end, all_points, depth + 1);

    // Compute the bounding box for the current node's subtree.
    // Start with the coordinates of the point stored in this node.
    const Point& current_point = all_points[node->point_idx];
    node->min_s = node->max_s = current_point.s;
    node->min_d = node->max_d = current_point.d;
    // Expand the bounding box to include the bounding boxes of the children subtrees.
    if (node->left) {
        node->min_s = std::min(node->min_s, node->left->min_s);
        node->max_s = std::max(node->max_s, node->left->max_s);
        node->min_d = std::min(node->min_d, node->left->min_d);
        node->max_d = std::max(node->max_d, node->left->max_d);
    }
    if (node->right) {
        node->min_s = std::min(node->min_s, node->right->min_s);
        node->max_s = std::max(node->max_s, node->right->max_s);
        node->min_d = std::min(node->min_d, node->right->min_d);
        node->max_d = std::max(node->max_d, node->right->max_d);
    }
    
    return node; // Return the newly created node.
}

// Global variable to store the minimum distance found during a single nearest neighbor query.
// Needs to be reset before each query.
long long current_min_dist; 

// Recursive function to find the nearest neighbor for a query point using the K-D tree.
void find_nearest_idx(KDNode* node, const Point& query_point, const std::vector<Point>& all_points, int depth) {
    // Base case: If the node is null, return.
    if (node == nullptr) {
        return; 
    }
    
    // Get the point stored in the current node.
    const Point& current_node_point = all_points[node->point_idx];

    // Calculate the distance from the query point to the point in the current node.
    // Update the global minimum distance if this point is closer and is not the query point itself.
    if (current_node_point.id != query_point.id) { 
        long long dist = chebyshev_dist(current_node_point, query_point);
        current_min_dist = std::min(current_min_dist, dist);
    }

    // Determine the splitting axis based on the current depth.
    int axis = depth % 2;
    KDNode *first_child, *second_child;
    
    // Decide which child subtree to explore first based on the query point's coordinate along the current axis.
    // We prioritize searching the subtree that contains the query point's coordinate.
    long long query_coord = (axis == 0) ? query_point.s : query_point.d;
    long long node_coord = (axis == 0) ? current_node_point.s : current_node_point.d;

    if (query_coord < node_coord) {
        first_child = node->left;
        second_child = node->right;
    } else {
        first_child = node->right;
        second_child = node->left;
    }

    // Recursively search the closer child subtree first.
    find_nearest_idx(first_child, query_point, all_points, depth + 1);

    // Check if the other ("further") subtree could possibly contain a closer point.
    // This is done by calculating the minimum possible distance from the query point to the bounding box of the other subtree.
    long long min_dist_to_bbox = 0;
    if (second_child != nullptr) {
         // Calculate the minimum distance along the S axis from the query point to the second child's bounding box.
         long long ds = 0; 
         if (query_point.s < second_child->min_s) ds = second_child->min_s - query_point.s;
         else if (query_point.s > second_child->max_s) ds = query_point.s - second_child->max_s;
         
         // Calculate the minimum distance along the D axis.
         long long dd = 0; 
         if (query_point.d < second_child->min_d) dd = second_child->min_d - query_point.d;
         else if (query_point.d > second_child->max_d) dd = query_point.d - second_child->max_d;
         
         // The minimum Chebyshev distance to the bounding box is the maximum of the distances along each axis.
         min_dist_to_bbox = std::max(ds, dd); 
    }
   
    // If the minimum distance to the second child's bounding box is less than the current minimum distance found so far,
    // then it's possible that a closer point exists in that subtree, so we need to explore it.
    if (second_child != nullptr && min_dist_to_bbox < current_min_dist) {
        find_nearest_idx(second_child, query_point, all_points, depth + 1);
    }
}

// Recursive function to delete the K-D tree and free allocated memory.
void delete_kdtree(KDNode* node) {
   if (!node) return;
   delete_kdtree(node->left);
   delete_kdtree(node->right);
   delete node;
}

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

    int N; // Number of points
    std::cin >> N;

    // Vector to store all points.
    std::vector<Point> points(N);
    // Variables to track the minimum and maximum S and D coordinates across all points.
    long long S_min = std::numeric_limits<long long>::max();
    long long S_max = std::numeric_limits<long long>::min();
    long long D_min = std::numeric_limits<long long>::max();
    long long D_max = std::numeric_limits<long long>::min();

    // Read input points, calculate transformed coordinates (s, d), and find the range of s and d values.
    for (int i = 0; i < N; ++i) {
        std::cin >> points[i].x >> points[i].y;
        points[i].s = points[i].x + points[i].y;
        points[i].d = points[i].x - points[i].y;
        points[i].id = i; // Store the original index.

        // Update min/max S and D values.
        S_min = std::min(S_min, points[i].s);
        S_max = std::max(S_max, points[i].s);
        D_min = std::min(D_min, points[i].d);
        D_max = std::max(D_max, points[i].d);
    }
    
    // Create a vector containing indices 0 to N-1. This will be used for building the K-D tree
    // without modifying the original points vector directly.
    std::vector<int> point_indices(N);
    std::iota(point_indices.begin(), point_indices.end(), 0); // Fills the vector with 0, 1, 2, ..., N-1.

    // Build the K-D tree using the indices vector and the points data.
    KDNode* root = build_kdtree_inplace(point_indices.begin(), point_indices.end(), points, 0);

    // Variable to store the minimum P_i value found across all points. Initialize to maximum possible value.
    long long min_P = std::numeric_limits<long long>::max();

    // Iterate through each point i to calculate its P_i value.
    for (int i = 0; i < N; ++i) {
        // Calculate M_i: the maximum Manhattan distance from point i to any other point.
        // This is equivalent to the maximum Chebyshev distance in the transformed (s, d) space.
        // The formula uses the distance from the point to the corners of the bounding box of all points.
        long long max_dist = std::max({points[i].s - S_min, S_max - points[i].s, points[i].d - D_min, D_max - points[i].d});

        // Calculate m_i: the minimum Manhattan distance from point i to any other point j (j != i).
        // Use the K-D tree to find the nearest neighbor in Chebyshev distance.
        current_min_dist = std::numeric_limits<long long>::max(); // Reset the global minimum distance tracker.
        find_nearest_idx(root, points[i], points, 0); // Perform the nearest neighbor search.
        long long min_dist = current_min_dist; // Get the result.
        
        // Calculate P_i = M_i - m_i, the difference between max and min distances.
        long long P_i = max_dist - min_dist;
        // Update the overall minimum P value found so far.
        min_P = std::min(min_P, P_i);
    }

    // Output the final minimum P value.
    std::cout << min_P << std::endl;
    
    // Free the memory allocated for the K-D tree nodes.
    delete_kdtree(root);

    return 0;
}