#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int construct_roads(vector<int> x, vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int, int>, int> mp;
vector<int> u, v, a, b;
vector<pair<int, int>> e;
int n = (int)x.size();
for(int i = 0; i < n; i++){
if(mp.count({x[i], y[i] - 2})){
e.push_back({mp[{x[i], y[i] - 2}], i});
}
if(mp.count({x[i], y[i] + 2})){
e.push_back({mp[{x[i], y[i] + 2}], i});
}
if(mp.count({x[i] - 2, y[i]})){
e.push_back({mp[{x[i] - 2, y[i]}], i});
}
if(mp.count({x[i] + 2, y[i]})){
e.push_back({mp[{x[i] + 2, y[i]}], i});
}
mp[{x[i], y[i]}] = i;
}
vector<int> par(n, -1);
function<int(int)> getpar = [&](int x){
return (par[x] < 0 ? x : par[x] = getpar(par[x]));
};
auto mrg = [&](int x, int y){
x = getpar(x), y = getpar(y);
if(x == y)return false;
if(par[x] > par[y])swap(x, y);
par[x] += par[y], par[y] = x;
return true;
};
auto cmp = [&](pair<int, int> a, pair<int, int> b){
auto [i1, j1] = a;
auto [i2, j2] = b;
if(x[i1] == x[j1]){
if(x[i2] == x[j2]){
return x[i1] < x[i2];
}
else{
return x[i1] < max(x[i2], x[j2]);
}
}
else{
if(x[i2] == x[j2]){
return min(x[i1], x[j1]) < x[i2];
}
else{
return min(x[i1], x[j1]) < min(x[i2], x[j2]);
}
}
};
auto cmp2 = [&](pair<int, int> a, pair<int, int> b){
auto [i1, j1] = a;
auto [i2, j2] = b;
if(x[i1] == x[j1]){
if(x[i2] == x[j2]){
return x[i1] < x[i2];
}
else{
return true;
}
}
else{
if(x[i2] == x[j2]){
return false;
}
else{
return min(x[i1], x[j1]) < min(x[i2], x[j2]);
}
}
};
auto op = e;
sort(op.begin(), op.end(), cmp2);
sort(e.begin(), e.end(), cmp);
map<pair<int, int>, bool> vis;
map<pair<int, int>, bool> tmp;
for(auto [i, j]: op){
tmp[{i, j}] = mrg(i, j);
}
for(auto [i, j]: e){
if(tmp[{i, j}]){
u.push_back(i), v.push_back(j);
if(x[i] == x[j]){
if(!vis.count({x[i] - 1, max(y[i], y[j]) - 1})){
vis[{x[i] - 1, max(y[i], y[j]) - 1}] = 1;
a.push_back(x[i] - 1);
b.push_back(max(y[i], y[j]) - 1);
}
else{
vis[{x[i] + 1, max(y[i], y[j]) - 1}] = 1;
a.push_back(x[i] + 1);
b.push_back(max(y[i], y[j]) - 1);
}
}
else{
if(!vis.count({max(x[i], x[j]) - 1, y[i] - 1})){
vis[{max(x[i], x[j]) - 1, y[i] - 1}] = 1;
a.push_back(max(x[i], x[j]) - 1);
b.push_back(y[i] - 1);
}
else{
vis[{max(x[i], x[j]) - 1, y[i] + 1}] = 1;
a.push_back(max(x[i], x[j]) - 1);
b.push_back(y[i] + 1);
}
}
}
}
int cnt = 0;
for(int i = 0; i < n; i++)cnt += par[i] < 0;
if(cnt > 1)return 0;
build(u, v, a, b);
return 1;
}
