#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
struct point {
int x,y,index;
};
bool dist(point x,point y){
if (pow(x.x - y.x,2)+pow(x.y-y.y,2)!=4)return false;
return true;
}
int binarysearch(int seg,int eq,int n,vector<point>arr){
int left = 0;
int right = n-1;
while(left<=right){
int mid = (left + right) >> 1;
if (arr[mid].x<seg)left= mid + 1;
else if (arr[mid].x>seg)right = mid-1;
else {
if (arr[mid].y<eq){
left=mid+1;
}
else if (arr[mid].y>eq){
right = mid-1;
}
else return mid;
}
}
return -1;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
vector<point>arr;
int n = x.size();
bool ok=true;
for (int i = 0 ;i<n;++i){
if (x[i]!=x[0])ok=false;
arr.push_back({x[i],y[i],i});
}
vector<int>ansx,ansy,ansxi,ansyi;
if (ok){
sort(arr.begin(),arr.end(),[&](point a,point b){
return a.y<b.y;
});
for (int i = 1;i<n;++i){
if (dist(arr[i],arr[i-1])){
ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
ansy.push_back(min(arr[i].y,arr[i-1].y)+1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[i-1].index);
}
else return 0;
}
build(ansxi,ansyi,ansx,ansy);
return 1;}
else{
vector<vector<bool>>p(3,vector<bool>(1e5 + 5,false));
sort(arr.begin(),arr.end(),[&](point a,point b){
if (a.x==b.x)return a.y<b.y;
return a.x<b.x;
});
set<int>check;
int i =1;
for (;i<n;++i){
if (arr[i].x!=2)break;
if (dist(arr[i],arr[i-1])){
ansx.push_back(min(arr[i].x,arr[i-1].x) - 1);
ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[i-1].index);
p[ansx.back()/2][ansy.back()/2]=true;
}
else {
int temp1 = binarysearch(arr[i].x+2,arr[i].y, n,arr);
if (temp1!=-1){
int first1 = min(arr[i].x,arr[temp1].x) + 1;
int second1 =min(arr[i].y,arr[temp1].y) + 1;
int second2 =min(arr[i].y,arr[temp1].y) - 1;
if (!p[first1/2][second1/2]){
ansx.push_back(first1);
ansy.push_back(second1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[temp1].index);
p[ansx.back()/2][ansy.back()/2]=true;
check.insert(temp1);
}
else if (!p[first1/2][second2/2]){
ansx.push_back(first1);
ansy.push_back(second2);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[temp1].index);
p[ansx.back()/2][ansy.back()/2]=true;
check.insert(temp1);
}
else return 0;
}
else return 0;
}
}
int j = i;
for (;i<n;++i){
if (arr[i-1].x==2)continue;
if (dist(arr[i],arr[i-1])){
ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[i-1].index);
p[ansx.back()/2][ansy.back()/2]=true;
}
else if (check.find(i)!=check.end())continue;
else {
int temp1 = binarysearch(arr[i].x-2,arr[i].y,n,arr);
if (temp1!=-1){
int first1 = min(arr[i].x,arr[temp1].x) + 1;
int second1 =min(arr[i].y,arr[temp1].y) + 1;
int second2 =min(arr[i].y,arr[temp1].y) - 1;
if (!p[first1/2][second1/2]){
ansx.push_back(first1);
ansy.push_back(second1);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[temp1].index);
p[ansx.back()/2][ansy.back()/2]=true;
}
else if (!p[first1/2][second2/2]){
ansx.push_back(first1);
ansy.push_back(second2);
ansxi.push_back(arr[i].index);
ansyi.push_back(arr[temp1].index);
p[ansx.back()/2][ansy.back()/2]=true;
}
else return 0;
}
else return 0;
}
}
bool ok=false;
for (i = j;i<n;++i){
if (dist(arr[j-1],arr[i])){
int first1=min(arr[i].x,arr[j-1].x) + 1;
int second1=min(arr[i].y,arr[j-1].y) + 1;
int second2 = min(arr[i].y,arr[j-1].y) - 1;
if (!p[first1/2][second1/2]){
ok=true;
ansx.push_back(first1);
ansy.push_back(second1);
ansxi.push_back(arr[j-1].index);
ansyi.push_back(arr[i].index);
break;
}
if (!p[first1/2][second2/2]){
ok=true;
ansx.push_back(first1);
ansy.push_back(second2);
ansxi.push_back(arr[j-1].index);
ansyi.push_back(arr[i].index);
break;
}
}
}
if (!ok)return 0;
build(ansxi,ansyi,ansx,ansy);
return 1;
}
}
