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