#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);
}
