#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int find(int i){
if(i == par[i]) return i;
else return par[i] = find(par[i]);
}
bool merge(int a, int b){
a = find(a), b = find(b);
if(a == b) return false;
par[a] = b;
return true;
}
pair<int, int> getBench(int x1, int y1, int x2, int y2){
if(x1 == x2){
pair<int, int> a = {x1+1, (y1+y2)/2}, b = {x1-1, (y1+y2)/2};
if((a.first + a.second) % 4 == 0) return a;
else return b;
}
else{
pair<int, int> a = {(x1+x2)/2, y1+1}, b = {(x1+x2)/2, y1-1};
if((a.first + a.second) % 4 == 2) return a;
else return b;
}
}
int construct_roads(vector<int> vx, vector<int> vy) {
if (vx.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = (int)vx.size();
par.resize(n);
for(int i = 0; i < n; i++) par[i] = i;
vector<tuple<int, int, int>> p;
map<pair<int, int>, int> mp;
for(int i = 0; i < n; i++){
p.emplace_back(vx[i], vy[i], i);
mp[make_pair(vx[i], vy[i])] = i;
}
int sz = 0;
set<pair<int, int>> benches;
sort(p.begin(), p.end());
vector<int> dx = {-2, 0}, dy = {0, -2};
vector<int> u, v, a, b;
for(auto [x, y, i] : p){
for(int j = 0; j < 2; j++){
int x2 = x+dx[j], y2 = y+dy[j];
if(!mp.count(make_pair(x2, y2))) continue;
int k = mp[make_pair(x2, y2)];
auto bench = getBench(x, y, x2, y2);
if(benches.count(bench)) continue;
if(merge(i, k)){
sz++;
u.push_back(i);
v.push_back(k);
a.push_back(bench.first);
b.push_back(bench.second);
benches.insert(bench);
}
}
}
if(sz != n-1) return 0;
build(u, v, a, b);
return 1;
}
