#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define X first
#define Y second
map<pair<int,int>, int> mapa,id,bancas;
lli n,p;
stack<pair<lli,lli> > pila;
pair<lli,lli> act,nuevo,mitad;
vector<int> u,v,a,b;
lli dir[8] = {0,2,0,-2,2,0,-2,0};
bool continua;
void construye(int U, int V, int A, int B) {
u.push_back(U);
v.push_back(V);
a.push_back(A);
b.push_back(B);
}
//quitar varios logs si no da en tiempo
int construct_roads(std::vector<int> x, std::vector<int> y) {
n = x.size();
act = {x[0],y[0]};
rep(i,0,n-1) {
nuevo = {x[i],y[i]};
mapa[nuevo] = 1;
id[nuevo] = i;
if (nuevo < act) act = nuevo;
}
pila.push(act);
while (!pila.empty()) {
act = pila.top();
mapa[act] = 2;
continua = false;
rep(i,0,3){
nuevo = act;
nuevo.X += dir[i];
nuevo.Y += dir[i+4];
p = mapa[nuevo];
if (p == 0 || p == 2) continue;
mitad.X = (act.X + nuevo.X)/2;
mitad.Y = (act.Y + nuevo.Y)/2;
if (i&1) {
//movimiento horizontal
mitad.Y++;
if (bancas[mitad] == 1) {
mitad.Y -= 2;
construye(id[act], id[nuevo], mitad.X, mitad.Y);
bancas[mitad] = 1;
pila.push(nuevo);
continua=true;
break;
}
mitad.Y -= 2;
if (bancas[mitad] == 1) {
mitad.Y += 2;
construye(id[act], id[nuevo], mitad.X, mitad.Y);
bancas[mitad] = 1;
pila.push(nuevo);
continua=true;
break;
}
}
else {
//movimiento vertical
mitad.X++;
if (bancas[mitad] == 1) {
mitad.X -= 2;
construye(id[act], id[nuevo], mitad.X, mitad.Y);
bancas[mitad] = 1;
pila.push(nuevo);
continua=true;
break;
}
mitad.X -= 2;
if (bancas[mitad] == 1) {
mitad.X += 2;
construye(id[act], id[nuevo], mitad.X, mitad.Y);
bancas[mitad] = 1;
pila.push(nuevo);
continua=true;
break;
}
}
}
if (continua) {
n--;
continue;
}
rep(i,0,3) {
nuevo = act;
nuevo.X += dir[i];
nuevo.Y += dir[i+4];
p = mapa[nuevo];
if (p == 0 || p == 2) continue;
mitad.X = (act.X + nuevo.X)/2;
mitad.Y = (act.Y + nuevo.Y)/2;
if (i&1) mitad.Y--;
else mitad.X++;
construye(id[act], id[nuevo], mitad.X, mitad.Y);
bancas[mitad] = 1;
pila.push(nuevo);
continua=true;
break;
}
if (continua) {
n--;
continue;
}
pila.pop();
}
if (n > 1) return 0;
build(u,v,a,b);
return 1;
}
