#include "parks.h"
#include <vector>
#include <map>
#include <set>
#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;
set<pii> st;
int dx2[] = {1, 1, -1, -1};
int dy2[] = {1, -1, 1, -1};
for (int i = 1; i <= N; i++) {
for (int k = 0; k < 4; k++) {
st.insert(make_pair(X[i] + dx2[k], Y[i] + dy2[k]));
}
}
for (pii p:st) {
bool flag = (p.first / 2 + p.second / 2) % 2;
int t1 = mp[{p.first - 1, p.second - 1}], t2 = flag ? mp[{p.first + 1, p.second - 1}] : mp[{p.first - 1, p.second + 1}];
if (t1 && t2) {
a.push_back(t1-1);
b.push_back(t2-1);
c.push_back(p.first);
d.push_back(p.second);
}
else {
int t3 = flag ? mp[{p.first - 1, p.second + 1}] : mp[{p.first + 1, p.second - 1}], t4 = mp[{p.first + 1, p.second + 1}];
if (t3 && t4) {
a.push_back(t3-1);
b.push_back(t4-1);
c.push_back(p.first);
d.push_back(p.second);
}
}
}
build(a, b, c, d);
return 1;
}
