#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int construct_roads(vector<int> x, vector<int> y) {
int N = x.size();
map<pair<int,int>,int> mp;
for(int i = 0;i < N;i++) mp[{x[i],y[i]}] = i;
vector<int> vis(N,false);
int dx[4] = {0,2,-2,0};
int dy[4] = {2,0,0,-2};
vector<int> u,v,a,b;
set<pair<int,int>> banned;
function<bool(int,int)> add_road = [&](int aidx,int bidx){
int midx = (x[aidx]+x[bidx])/2;
int midy = (y[aidx]+y[bidx])/2;
if(x[aidx] == x[bidx]){
// vertical
if((midy/2)%2 == (midx/2)%2){
midx++;
}else{
midx--;
}
}else{
// horizontal
if((midx/2)%2 == (midy/2)%2){
midy--;
}else{
midy++;
}
}
if(banned.count({midx,midy})) return false;
banned.insert({midx,midy});
// {
// int nidx1 = -1,nidx2 = -1;
// for(int d = 0;d < 4;d++){
// int nx = midx+dx[d]/2;
// int ny = midy+dy[d]/2;
// if(nx == x[aidx] && ny == y[aidx]) continue;
// if(nx == x[bidx] && ny == y[bidx]) continue;
// if(mp.count({nx,ny})){
// if(nidx1 == -1) nidx1 = mp[{nx,ny}];
// else nidx2 = mp[{nx,ny}];
// }
// }
// if(nidx1 != -1 && nidx2 != -1){
// vis[nidx1] = true;
// vis[nidx2] = true;
// if(x[aidx] == x[nidx1] || y[aidx] == y[nidx1]){
// add_road(aidx,nidx1);
// add_road(bidx,nidx2);
// }else{
// add_road(aidx,nidx2);
// add_road(bidx,nidx1);
// }
// }
// }
u.push_back(aidx);
v.push_back(bidx);
a.push_back(midx);
b.push_back(midy);
return true;
};
auto doit = [&](int start){
u.clear(),v.clear(),a.clear(),b.clear();
banned.clear();
vis = vector<int>(N,false);
queue<int> q;
q.push(start);
while(!q.empty()){
int idx = q.front();
q.pop();
vis[idx] = true;
int cx = x[idx],cy = y[idx];
for(int d = 0;d < 4;d++){
int nx = cx+dx[d];
int ny = cy+dy[d];
if(!mp.count({nx,ny})) continue;
int nidx = mp[{nx,ny}];
if(vis[nidx]) continue;
if(add_road(idx,nidx)) q.push(nidx);
}
}
for(auto &i:vis){
if(!i) return false;
}
build(u,v,a,b);
return true;
};
vector<int> perm(N);
for(int i = 0;i < N;i++) perm[i] = i;
shuffle(perm.begin(),perm.end(),rng);
for(int i = 0;i < 3;i++){
if(doit(perm[i])) return true;
}
return false;
}
