#include "parks.h"
#include <vector>
#include <map>
#include <functional>
using namespace std;
using pii = pair<int, int>;
struct UnionFind
{
vector<int> par;
UnionFind(int N)
{
par.resize(N+1);
for (int i = 0; i <= N; i++) par[i] = i;
}
int fin(int v)
{
return v == par[v] ? v : (par[v] = fin(par[v]));
}
void uni(int u, int v)
{
par[fin(u)] = fin(v);
}
bool isuni(int u, int v)
{
return fin(u) == fin(v);
}
};
int X[200005], Y[200005];
vector<int> adj[200005];
bool visited[200005];
pair<int, int> tilt(pair<int, int> ori, int pv)
{
if (ori == make_pair(1, 0)) return make_pair(0, -pv);
else if (ori == make_pair(0, 1)) return make_pair(pv, 0);
else if (ori == make_pair(-1, 0)) return make_pair(0, pv);
else return make_pair(-pv, 0);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int N = x.size();
map<pii, int> mp;
for (int i = 1; i <= N; i++) {
X[i] = x[i-1], Y[i] = y[i-1];
}
for (int i = 1; i <= N; i++) {
mp[make_pair(X[i], Y[i])] = i;
}
UnionFind uf(N);
int dx[] = {-2, 2, 0, 0};
int dy[] = {0, 0, -2, 2};
for (int i = 1; i <= N; i++) {
for (int k = 0; k < 4; k++) {
int nx = X[i] + dx[k], ny = Y[i] + dy[k];
int tmp = mp[make_pair(nx, ny)];
if (tmp) {
adj[i].push_back(tmp);
uf.uni(i, tmp);
}
}
}
for (int i = 1; i <= N; i++) {
if (!uf.isuni(1, i)) return 0;
}
vector<int> a, b, c, d;
function<void(int, int)> dfs = [&](int v, int depth)
{
visited[v] = true;
for (int i:adj[v]) {
if (visited[i]) continue;
int mx = X[v] + X[i] >> 1, my = Y[v] + Y[i] >> 1;
pair<int, int> ori = make_pair((X[i] - X[v]) / 2, (Y[i] - Y[v]) / 2);
pair<int, int> nxt = tilt(ori, (depth % 2) * 2 - 1);
a.push_back(v-1);
b.push_back(i-1);
c.push_back(mx + nxt.first);
d.push_back(my + nxt.second);
dfs(i, depth + 1);
}
};
dfs(1, 0);
build(a, b, c, d);
return 1;
}
