#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
struct Po {
int x, y, f;
};
bool operator<(const Po& l, const Po& r) {
return tie(l.x, l.y) < tie(r.x, r.y);
}
bool operator==(const Po& l, const Po& r) {
return tie(l.x, l.y) == tie(r.x, r.y);
}
struct Ed {
int s, t;
Po be;
};
int find(int x, vector<int>& p) {
if (p[x] == x) return x;
return p[x] = find(p[x], p);
}
void unite(int a, int b, vector<int>& p) {
a = find(a, p);
b = find(b, p);
p[a] = b;
}
using g_t = map<Po, set<Po>>;
int construct_roads(std::vector<int> x, std::vector<int> y) {
vector<int> p(x.size());
set<Po> par;
for (int i = 0; i < x.size(); ++i) {
p[i] = i;
par.insert({x[i], y[i], i});
}
vector<Ed> eds;
for (int i = 0; i < x.size(); ++i) {
if (par.find({x[i], y[i] + 2}) != par.end() && find(par.find({x[i], y[i] + 2})->f, p) != find(i, p)) {
eds.push_back({par.find({x[i], y[i] + 2})->f, i});
unite(par.find({x[i], y[i] + 2})->f, i, p);
}
if (par.find({x[i] + 2, y[i]}) != par.end() && find(par.find({x[i] + 2, y[i]})->f, p) != find(i, p)) {
eds.push_back({par.find({x[i] + 2, y[i]})->f, i});
unite(par.find({x[i] + 2, y[i]})->f, i, p);
}
}
if (eds.size() + 1 < x.size()) return 0;
g_t g;
for (int j = 0; j < eds.size(); ++j) {
if (x[eds[j].s] == x[eds[j].t]) {
g[{x[eds[j].s] + 1, (y[eds[j].s] + y[eds[j].t])/2}].insert({x[eds[j].s] - 1,(y[eds[j].s] + y[eds[j].t])/2, j});
g[{x[eds[j].s] - 1, (y[eds[j].s] + y[eds[j].t])/2}].insert({x[eds[j].s] + 1,(y[eds[j].s] + y[eds[j].t])/2, j});
} else {
g[{(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] + 1}].insert({(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] - 1, j});
g[{(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] - 1}].insert({(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] + 1, j});
}
}
queue<Po> ne;
for (auto [st, en]: g) {
if (en.size() == 1) ne.push(st);
}
while (!ne.empty()) {
auto to = ne.front();
ne.pop();
if (g[to].empty()) {
g.erase(to);
continue;
}
eds[g[to].begin()->f].be = to;
g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
g.erase(to);
}
while (!g.empty()) {
if (g.begin()->second.empty()) g.erase(g.begin());
else {
assert(g.begin()->second.size() == 2);
auto to = g.begin()->first;
eds[g[to].begin()->f].be = to;
g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
while (!ne.empty()) {
to = ne.front();
ne.pop();
if (g[to].empty()) {
g.erase(to);
continue;
}
eds[g[to].begin()->f].be = to;
g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
g.erase(to);
}
}
}
vector<int> u(eds.size()), v(eds.size()), a(eds.size()), b(eds.size());
for (int i = 0; i < eds.size(); ++i) {
tie(u[i], v[i], a[i], b[i]) = tie(eds[i].s, eds[i].t, eds[i].be.x, eds[i].be.y);
}
build(u, v, a, b);
return 1;
}
