#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(s) ((int)s.size())
typedef array<int, 2> ar2;
// set<ar2> pts;
map<ar2, ar2> edges;
map<ar2, int> pts;
// set<ar2> edges;
set<ar2> vis;
int n;
vector<int> u, v, a, b;
set<ar2> matched;
vector<ar2> adj2({{2, 0}, {0, 2}, {-2, 0}, {0, -2}});
vector<ar2> adj({{1, 0}, {0, 1}, {-1, 0}, {0, -1}});
ar2 operator+(ar2 a, ar2 b) {
return {a[0]+b[0], a[1]+b[1]};
}
ar2 operator-(ar2 a, ar2 b) {
return {a[0]-b[0], a[1]-b[1]};
}
void dfs(ar2 cur) {
vis.insert(cur);
for (int i = 0; i < 4; i++) {
ar2 nxt = cur+adj2[i];
if (pts.find(nxt) == pts.end() || vis.find(nxt) != vis.end()) {
continue;
}
ar2 epos = cur+adj[i];
// edges.insert(epos);
edges[epos] = {pts[cur], pts[nxt]};
dfs(nxt);
}
}
bool is_real(ar2 &square) {
int s = 0;
for (ar2 v1: adj) s += (edges.find(square+v1) != edges.end());
return s <= 2;
}
void match(ar2 e);
bool match(ar2 edge, ar2 sq) {
bool comp = !is_real(sq);
bool virt = ((edge[1]&1)&&comp);
if (virt) sq = {-sq[0], -sq[1]};
if (matched.find(sq) != matched.end()) return 0;
if (!virt) {
u.push_back(edges[edge][0]);
v.push_back(edges[edge][1]);
a.push_back(sq[0]);
b.push_back(sq[1]);
}
matched.insert(sq);
matched.insert(edge);
if (comp) match(sq+sq-edge); // must exist
else {
for (ar2 v1: adj) {
if (edges.find(sq+v1) != edges.end() && matched.find(sq+v1) == matched.end()) match(sq+v1);
}
}
return 1;
}
void match(ar2 edge) {
if (matched.find(edge) != matched.end()) return;
if (edge[0]&1) { // horizontal edge
if (!match(edge, edge+ar2({0,1}))) assert(match(edge, edge+ar2({0, -1})));
}
else if (!match(edge, edge+ar2({1, 0}))) assert(match(edge, edge+ar2({-1, 0})));
}
int construct_roads(vector<int> x, vector<int> y) {
n = sz(x);
for (int i = 0; i < n; i++) {
// pts.insert({x[i], y[i]});
pts[{x[i], y[i]}] = i;
}
dfs({x[0], y[0]});
if (sz(vis) != n) return 0;
for (auto v: edges) match(v.first);
build(u, v, a, b);
return 1;
}
