#include <bits/stdc++.h> using namespace std; // Assumes points are sorted by X then Y // Always makes cuts horizontally vector<pair<uint32_t, vector<size_t>>> to_tree(vector<pair<int32_t, int32_t>> points) { vector<pair<uint32_t, vector<size_t>>> tree; vector<tuple<int32_t, int32_t, size_t>> ranges; // Group points by X coordinate size_t i = 0; while (i < points.size()) { int32_t current_x = points[i].first; vector<pair<int32_t, int32_t>> x_chunk; while (i < points.size() && points[i].first == current_x) { x_chunk.push_back(points[i]); i++; } vector<tuple<int32_t, int32_t, size_t>> new_ranges; size_t closest_range = 0; // Group x_chunk by consecutive Y coordinates size_t j = 0; while (j < x_chunk.size()) { int32_t min_y = x_chunk[j].second; int32_t max_y = min_y; while (j + 1 < x_chunk.size() && x_chunk[j + 1].second == x_chunk[j].second + 1) { j++; max_y = x_chunk[j].second; } size_t node_idx = tree.size(); uint32_t height = (uint32_t)abs(max_y - min_y) + 1; vector<size_t> children; while (closest_range < ranges.size()) { int32_t closest_min_x = get<0>(ranges[closest_range]); int32_t closest_max_x = get<1>(ranges[closest_range]); size_t closest_node = get<2>(ranges[closest_range]); if (closest_min_x <= max_y && closest_max_x >= min_y) { children.push_back(closest_node); tree[closest_node].second.push_back(node_idx); } if (closest_max_x >= max_y) break; closest_range++; } tree.push_back({height, children}); new_ranges.push_back({min_y, max_y, node_idx}); j++; } ranges = new_ranges; } return tree; } uint32_t calculate_result_for_tree(uint32_t total_points, vector<pair<uint32_t, vector<size_t>>>& tree, uint32_t modulo) { vector<size_t> to_evaluate; uint32_t sum = 0; // Find all leaf nodes (nodes with only 1 connection) for (size_t idx = 0; idx < tree.size(); idx++) { if (tree[idx].second.size() == 1) { to_evaluate.push_back(idx); } } while (!to_evaluate.empty()) { size_t node_idx = to_evaluate.back(); to_evaluate.pop_back(); auto node = tree[node_idx]; sum = (sum + (uint64_t)node.first * (total_points - node.first)) % modulo; // Remove this node from its neighbors for (size_t neighbour : node.second) { // Remove node_idx from neighbour's children auto& neighbour_children = tree[neighbour].second; neighbour_children.erase( remove(neighbour_children.begin(), neighbour_children.end(), node_idx), neighbour_children.end() ); tree[neighbour].first += node.first; if (tree[neighbour].second.size() == 1) { to_evaluate.push_back(neighbour); } } } return sum; } uint32_t solve(vector<pair<int32_t, int32_t>> points, uint32_t modulo) { uint32_t total_points = points.size(); // Horizontal sort vector<pair<int32_t, int32_t>> horizontal_sort = points; sort(horizontal_sort.begin(), horizontal_sort.end()); vector<pair<uint32_t, vector<size_t>>> horizontal_tree = to_tree(horizontal_sort); uint32_t horizontal_value = calculate_result_for_tree(total_points, horizontal_tree, modulo); // Vertical sort vector<pair<int32_t, int32_t>> vertical_sort; for (auto& p : points) { vertical_sort.push_back({p.second, p.first}); } sort(vertical_sort.begin(), vertical_sort.end()); vector<pair<uint32_t, vector<size_t>>> vertical_tree = to_tree(vertical_sort); uint32_t vertical_value = calculate_result_for_tree(total_points, vertical_tree, modulo); return (horizontal_value + vertical_value) % modulo; } int DistanceSum(int N, int *X, int *Y) { vector<pair<int32_t, int32_t>> points; for (int i = 0; i < N; i++) { points.push_back({X[i], Y[i]}); } return solve(points, 1000000000); }