#include <bits/stdc++.h>
#include "parks.h"
std::unordered_map<int, int> map[200001];
int construct_roads(std::vector<int> x, std::vector<int> y) {
int N = (int) x.size();
if (N == 1) {
build({}, {}, {}, {});
return 1;
}
int maxx = x[0];
int minx = x[0];
for (int i = 0; i < N; ++i) {
maxx = std::max(maxx, x[i]);
minx = std::min(minx, x[i]);
}
std::vector<int> u, v, a, b;
for (int i = 0; i < N; ++i) {
map[x[i]][y[i]] = i;
}
bool seen[N];
for (int i = 0; i < N; ++i) {
seen[i] = false;
}
std::queue<int> bfs;
bfs.push(0);
seen[0] = true;
auto add = [&](int x, int y, std::vector<int> &data) {
if (x < 0 || x > 200000) return;
if (map[x].count(y)) data.push_back(map[x][y]);
};
auto edges = [&](int x, int y) {
std::vector<int> result;
add(x, y + 2, result);
add(x, y - 2, result);
add(x + 2, y, result);
add(x - 2, y, result);
return result;
};
int rem = N - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto n: edges(x[next], y[next])) {
if (!seen[n]) {
seen[n] = true;
bfs.push(n);
rem--;
u.push_back(next);
v.push_back(n);
}
}
}
if (rem)
return 0;
std::function<std::vector<std::pair<int, int>>(int, int)> valid = [&x, &y, minx, maxx](int u,
int v) -> std::vector<std::pair<int, int>> {
if (x[u] == x[v]) {
int _y = (y[u] + y[v]) / 2;
if (x[u] == minx) return {{minx - 1, _y}};
if (x[u] == maxx) return {{maxx + 1, _y}};
return {{x[u] + 1, _y},
{x[u] - 1, _y}};
} else {
int _x = (x[u] + x[v]) / 2;
return {{_x, y[u] + 1},
{_x, y[u] - 1}};
}
};
std::vector<std::pair<int, int>> vld[N - 1];
for (int i = 0; i < N - 1; ++i) {
vld[i] = valid(u[i], v[i]);
a.push_back(vld[i][0].first);
b.push_back(vld[i][0].second);
}
build(u, v, a, b);
return 1;
}
