#include "parks.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
vector<int> bo,ss;
void init(int x){
bo.resize(x);
ss.resize(x,1);
iota(bo.begin(),bo.end(),0);
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
int merge(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return 0;
}
bo[x]=y;
ss[y]+=ss[x];
return 1;
}
}dsu;
vector<int> au,av,aa,ab;
void ag(int a,int b,int c,int d){
au.push_back(a);
av.push_back(b);
aa.push_back(c);
ab.push_back(d);
}
map<pair<int,int>,int> pt,cn;
vector<pair<int,int> > tl;
vector<vector<int> > eg;
vector<int> se,vis;
int cnt=0;
void add(pair<int,int> a,pair<int,int> x){
if(a.fs>a.sc){
swap(a.fs,a.sc);
}
if(cn.find(a)==cn.end()){
cn[a]=cnt;
cnt++;
eg.push_back(vector<int>());
tl.push_back(a);
se.push_back(0);
}
if(pt.find(x)==pt.end()){
pt[x]=cnt;
cnt++;
eg.push_back(vector<int>());
tl.push_back(x);
se.push_back(1);
}
//cout << cn[a] << " " << pt[x] << "\n";
eg[cn[a]].push_back(pt[x]);
eg[pt[x]].push_back(cn[a]);
}
void dfs(int r){
vis[r]=1;
int p=0;
for(auto h:eg[r]){
if(vis[h]==0){
vis[h]=1;
p=h;
ag(tl[r].fs,tl[r].sc,tl[h].fs,tl[h].sc);
break;
}
}
for(auto h:eg[p]){
if(vis[h]==0){
dfs(h);
}
}
}
int construct_roads(vector<int> x, vector<int> y) {
cn.clear();
pt.clear();
eg.clear();
se.clear();
tl.clear();
vis.clear();
cnt=0;
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int,int>,int> mp;
int n=x.size();
for(int i=0;i<n;i++){
mp[{x[i],y[i]}]=i;
}
dsu.init(n);
const int dx[4]={0,0,2,-2},dy[4]={2,-2,0,0};
for(int p=0;p<n;p++){
for(int k=0;k<4;k++){
int c=x[p]+dx[k],d=y[p]+dy[k];
if(mp.find({c,d})!=mp.end()){
int a=mp[{c,d}];
if(dsu.merge(a,p)){
if(x[a]==x[p]){
int u=(y[a]+y[p])/2;
add({a,p},{x[a]-1,u});
add({a,p},{x[a]+1,u});
}
else{
int u=(x[a]+x[p])/2;
add({a,p},{u,y[a]-1});
add({a,p},{u,y[a]+1});
}
}
}
}
}
if(dsu.ss[dsu.find(0)]!=n){
return 0;
}
vis.resize(cnt);
for(int i=0;i<cnt;i++){
if(se[i]==0 && !vis[i]){
dfs(i);
}
}
build(au,av,aa,ab);
return 1;
}
