#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
int DX[] = {-1, 0, 1, 0};
int DY[] = {0, 1, 0, -1};
const int MV = 1e9;
struct DSU {
int nrc;
vi e;
DSU(int n) : nrc(n), e(n, -1) {}
int repr(int u) {
while(e[u] >= 0) u = e[u];
return u;
}
void join(int u, int v) {
u = repr(u); v = repr(v);
if(u == v) return;
if(e[u] >= e[v]) swap(u, v);
e[u] += e[v];
e[v] = u;
--nrc;
}
};
int construct_roads(vi x, vi y) {
auto get_bench_coord = [&](int u, int v) -> pair<ii, ii> {
int xcm = (x[u] + x[v]) / 2, ycm = (y[u] + y[v]) / 2;
int dx = 2 - abs(x[u] - x[v]), dy = 2 - abs(y[u] - y[v]);
return make_pair(ii{xcm - dx / 2, ycm - dy / 2}, ii{xcm + dx / 2, ycm + dy / 2});
};
int n = x.size();
vector<ii> B;
map<ii, int> Id;
for(int i = 0; i < n; ++i)
Id[ii{x[i], y[i]}] = i;
for(int i = 0; i < n; ++i) {
for(int d = 0; d < 4; ++d) {
int nx = x[i] + 2 * DX[d], ny = y[i] + 2 * DY[d];
if(Id.count({nx, ny})) {
int u = Id[{nx, ny}];
auto [a, b] = get_bench_coord(u, i);
B.push_back(a);
B.push_back(b);
}
}
}
sort(B.begin(), B.end());
B.resize(unique(B.begin(), B.end()) - B.begin());
map<ii, int> IdB;
int m = B.size();
for(int i = 0; i < m; ++i) {
IdB[B[i]] = i;
}
vi U, V, RA, RB;
DSU Sol(n);
auto leaga = [&](int x, int y, int x1, int y1, int x2, int y2) -> bool {
if(Id.count({x1, y1}) && Id.count({x2, y2})) {
int u = Id[{x1, y1}], v = Id[{x2, y2}];
U.push_back(u);
V.push_back(v);
RA.push_back(x);
RB.push_back(y);
Sol.join(u, v);
return true;
}
return false;
};
for(int i = 0; i < m; ++i) {
auto [x, y] = B[i];
int tip = ((((x + MV) / 2) & 1) + (((y + MV) / 2) & 1)) % 2;
if(tip) {
//leg la ceva vertical
leaga(x, y, x + 1, y - 1, x + 1, y + 1) ||
leaga(x, y, x - 1, y - 1, x - 1, y + 1);
} else {
//leg la ceva orizontal
leaga(x, y, x - 1, y + 1, x + 1, y + 1) ||
leaga(x, y, x - 1, y - 1, x + 1, y - 1);
}
}
if(Sol.nrc != 1) return 0;
build(U, V, RA, RB);
return 1;
}
