結果
| 問題 |
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;
}