#include "parks.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ii pair<int,int>
using namespace std;
#define maxn 200010
#define db(x) cerr<<#x<<": "<<(x)<<"\n";
int mx[4] = { 0 , 2 , 0 , -2 };
int my[4] = { 2 , 0 , -2 , 0 };
int vis[maxn];
ii arr[maxn];
map<ii,int> mk;
vector<int> U, V, A, B;
map<ii,int> mp;
bool add_edge(int u,int v,int plus_){
U.push_back(u);
V.push_back(v);
if( arr[u].f != arr[v].f ){
if( mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] ) return false;
A.push_back( (arr[u].f+arr[v].f)/2 );
B.push_back( arr[u].s + plus_ );
mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] = true;
}
else{
if( mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] ) return false;
A.push_back( arr[u].f + plus_ );
B.push_back( (arr[u].s+arr[v].s)/2 );
mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] = true;
}
return true;
}
void dfs(int u,int p,int plus_){
vis[u] = 1;
for(int i=0; i<4; i++){
int nx = arr[u].f + mx[i];
int ny = arr[u].s + my[i];
if( mp[{nx,ny}] ){
int v = mp[{nx,ny}] - 1;
if( vis[v] ) continue;
int gp = p / 2 * 2 + ( p + 1 ) % 2;
int nplus = plus_;
if( i != gp ) nplus *= -1;
if( add_edge(u,v,nplus) )
dfs(v,i,nplus);
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
// if (x.size() == 1) {
// vector<int> pra;
// build(pra, pra, pra, pra);
// return 1;
// }
int n = x.size();
pair<ii,int> st = { { 2000000007 , 2000000007 } , -1 };
for(int i=0; i<n; i++){
arr[i] = {x[i],y[i]};
mp[{x[i],y[i]}] = i + 1;
st = min( st , { arr[i] , i } );
}
int u = st.s;
vis[u] = 1;
for(int i=0; i<4; i++){
int nx = arr[u].f + mx[i];
int ny = arr[u].s + my[i];
if( mp[{nx,ny}] ){
int v = mp[{nx,ny}] - 1;
if( vis[v] ) continue;
int plus_ = ( i == 1 ) + ( i == 2 ) - ( i == 0 ) - ( i == 3 );
if( add_edge(u,v,plus_) )
dfs(v,i,plus_);
}
}
for(int i=0; i<n; i++)
if( vis[i] == 0 )
return 0;
build(U, V, A, B);
return 1;
}
