#include "parks.h"
#include <map>
#include <set>
#include <utility>
using pii = std::pair<int, int>;
#define ff first
#define ss second
const int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
const int MN = 2e5+10;
int ctr, N;
bool v[MN];
pii pt[MN];
std::map<pii, int> map;
std::set<pii> bloc;
void dfs(int n)
{
if(v[n]) return;
v[n]=1, ++ctr;
pii x = pt[n];
for(int i=0;i<4;++i)
{
pii o(x.ff+2*dx[i], x.ss+2*dy[i]);
if(map.find(o) != map.end())
dfs(map[o]);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
N = x.size();
for(int i=0;i<N;++i)
{
pt[i]={x[i], y[i]};
map[pt[i]]=i;
bloc.insert({x[i]-1, y[i]-1});
bloc.insert({x[i]+1, y[i]-1});
bloc.insert({x[i]-1, y[i]+1});
bloc.insert({x[i]+1, y[i]+1});
}
dfs(0);
if(ctr < N) return 0;
std::vector<int> u, v, a, b;
for(auto x:bloc)
{
int d = x.ff+x.ss&3 ? 1 : -1;
pii p1(x.ff+1, x.ss+d);
pii p2(x.ff-d, x.ss+1);
pii p3(x.ff-1, x.ss-d);
pii p4(x.ff+d, x.ss-1);
if(map.find(p1) != map.end() && map.find(p2) != map.end())
u.push_back(map[p1]), v.push_back(map[p2]), a.push_back(x.ff), b.push_back(x.ss);
else if(map.find(p3) != map.end() && map.find(p4) != map.end())
u.push_back(map[p3]), v.push_back(map[p4]), a.push_back(x.ff), b.push_back(x.ss);
}
build(u, v, a, b);
return 1;
}
