#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
const int MAX_N=2e5+10;
struct point{
int x,y,id;
point(int xx,int yy,int ii){
x=xx;
y=yy;
id=ii;
}
ii coord(){
return ii(x,y);
}
};
struct Road{
int u,v,id;
bool hor;
Road(int uu,int vv,int ii,bool h){
u=uu; v=vv; id=ii; hor=h;
}
};
int pa[MAX_N];
int n;
vector<point> foun;
vector<Road> road;
int X[5]={0,1,0,-1};
int Y[5]={-1,0,1,0};
int ns=0;
void init(int n){
for(int i=0;i<n;i++) pa[i]=i;
ns=n;
}
int findset(int u){
return pa[u]==u?u:pa[u]=findset(pa[u]);
}
bool issameset(int i,int j){
return findset(i)==findset(j);
}
void unionset(int i,int j){
if(!issameset(i,j)){
int u=findset(i),v=findset(j);
pa[u]=v;
ns--;
}
}
set<ii> us;
vector<ii> puntosChoque(int id){
vector<ii> pu;
ii f1=foun[road[id].u].coord();
ii f2=foun[road[id].v].coord();
int x,y;
if(f1.second==f2.second){
x=(f1.first+f2.first)/2;
y=f1.second;
}
else{
x=f1.first;
y=(f1.second+f2.second)/2;
}
for(int i=0;i<4;i++){
int xk=x+X[i];
int yk=y+Y[i];
if(us.find(ii(xk,yk))!=us.end()) continue;
if(ii(xk,yk)!=f1 && ii(xk,yk)!=f2)
pu.push_back(ii(xk,yk));
}
return pu;
}
bool canConnect(point u,point v){
return !issameset(u.id,v.id) && (((u.x==v.x && abs(u.y-v.y)==2)) || ((u.y==v.y && abs(u.x-v.x)==2)));
}
bool don[MAX_N];
bool sortX(point a,point b){
return a.x!=b.x ? a.x<b.x: a.y<b.y;
}
bool sortY(point a,point b){
return a.y!=b.y ? a.y<b.y : a.x<b.x;
}
bool origin(point a,point b){
return a.id<b.id;
}
int be;
map<ii,int> punid;
map<int,ii> idpun;
map<int,vi> conbe;
void choque(int id){
vector<ii> pu=puntosChoque(id);
for(int i=0;i<pu.size();i++){
if(punid.find(pu[i])==punid.end()){
punid[pu[i]]=be;
idpun[id]=pu[i];
be++;
}
conbe[punid[pu[i]]].push_back(id);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
n=x.size();
for(int i=0;i<n;i++){
foun.push_back(point(x[i],y[i],i));
}
init(n);
sort(foun.begin(),foun.end(),sortX);
vector<int> ua,va;
for(int i=0;i<n-1;i++){
if(canConnect(foun[i],foun[i+1])){
unionset(foun[i].id,foun[i+1].id);
ua.push_back(foun[i].id);
va.push_back(foun[i+1].id);
road.push_back(Road(foun[i].id,foun[i+1].id,road.size(),0));
}
}
sort(foun.begin(),foun.end(),sortY);
for(int i=0;i<n-1;i++){
if(canConnect(foun[i],foun[i+1])){
unionset(foun[i].id,foun[i+1].id);
ua.push_back(foun[i].id);
va.push_back(foun[i+1].id);
road.push_back(Road(foun[i].id,foun[i+1].id,road.size(),1));
}
}
sort(foun.begin(),foun.end(),origin);
if(ns!=1) return 0;
be=road.size();
for(int i=0;i<road.size();i++) choque(i);
priority_queue<ii, vector<ii>, greater<ii> > pq;
for(int i=0;i<road.size();i++){
int pro=0;
vector<ii> pu=puntosChoque(i);
for(int j=0;j<pu.size();j++){
int v=punid[pu[j]];
pq.push(ii(conbe[v].size(),i));
}
}
/*for(int i=0;i<road.size();i++){
cout<<road[i].u<<" "<<road[i].v<<endl;
}*/
int t=road.size();
vector<int> a(t),b(t);
while(!pq.empty()){
int i=pq.top().second;
pq.pop();
if(don[i]) continue;
vector<ii> pu=puntosChoque(i);
int iu=0;
//cout<<i<<": \n";
for(int j=0;j<pu.size();j++){
int u=punid[pu[j]];
int vis=0;
//cout<<pu[j].first<<" "<<pu[j].second<<":\n";
for(auto &v:conbe[u]){
// cout<<v<<endl;
if(!don[v]) vis++;
}
if(vis==1){
iu=j;
break;
}
}
don[i]=1;
// cout<<endl;
us.insert(pu[iu]);
a[i]=pu[iu].first; b[i]=pu[iu].second;
for(int j=0;j<pu.size();j++){
int vis=0;
int u=punid[pu[j]];
int id=-1;
for(auto &v:conbe[u]){
if(!don[v]){
id=v;
vis++;
}
}
if(vis==1){
pq.push(ii(1,id));
}
}
}
build(ua,va,a,b);
return 1;
}
