#include "parks.h"
#include <vector>
#include <set>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxN = 200'000;
int N;
vector<int> X, Y;
vector<int> fountain_edge[maxN];
vector<int> fountain_visit(maxN, 0);
int visit_count = 0;
void fountain_dfs(int u)
{
fountain_visit[u] = 1;
visit_count++;
for(int v: fountain_edge[u])
{
if(fountain_visit[v]) continue;
fountain_dfs(v);
}
}
struct obj
{
int i;
int x;
int y;
};
bool operator < (obj A, obj B)
{
if(A.x == B.x) return A.y < B.y;
return A.x < B.x;
};
set<obj> fountains;
set<obj> benches;
int point_index(int x, int y)
{
set<obj>::iterator it = fountains.find(obj{-1, x, y});
if(it == fountains.end()) return -1;
else return it->i;
}
int bench_id = -1;
void insert_bench(int x, int y)
{
set<obj>::iterator it = benches.find(obj{-1, x, y});
if(it == benches.end())
{
bench_id++;
benches.insert(obj{bench_id, x, y});
}
}
vector<int> U, V, A, B;
void add_edge(int u, int v, int a, int b)
{
// printf("add_edge %d(%d, %d) - %d(%d, %d) with bench at (%d, %d) \n", u, X[u], Y[u], v, X[v], Y[v], a, b);
U.push_back(u);
V.push_back(v);
A.push_back(a);
B.push_back(b);
}
int construct_roads(vector<int> x, vector<int> y)
{
// cerr << "check\n";
X = x;
Y = y;
N = X.size();
for(int i = 0; i < N; i++)
fountains.insert(obj{i, x[i], y[i]});
for(int i = 0; i < N; i++)
{
int I;
I = point_index(x[i] - 2, y[i]);
if(I != -1)
{
fountain_edge[i].push_back(I);
fountain_edge[I].push_back(i);
}
I = point_index(x[i], y[i] - 2);
if(I != -1)
{
fountain_edge[i].push_back(I);
fountain_edge[I].push_back(i);
}
insert_bench(x[i] - 1, y[i] - 1);
insert_bench(x[i] + 1, y[i] - 1);
insert_bench(x[i] - 1, y[i] + 1);
insert_bench(x[i] + 1, y[i] + 1);
}
fountain_dfs(0);
if(visit_count != N)
{
return 0;
}
for(obj B: benches)
{
// cerr << "B = " << B.x << ' ' << B.y << '\n';
int P1, P2;
if((B.x + B.y) % 4 == 0) //horizontal
{
// cerr << "horizontal\n";
P1 = point_index(B.x - 1, B.y - 1);
P2 = point_index(B.x + 1, B.y - 1);
if(P1 != -1 && P2 != -1)
{
add_edge(P1, P2, B.x, B.y);
continue;
}
P1 = point_index(B.x - 1, B.y + 1);
P2 = point_index(B.x + 1, B.y + 1);
if(P1 != -1 && P2 != -1)
add_edge(P1, P2, B.x, B.y);
}
else
{
// cerr << "vertical\n";
P1 = point_index(B.x - 1, B.y - 1);
P2 = point_index(B.x - 1, B.y + 1);
// cerr << B.x - 1 << ' ' << B.y - 1 << " " << B.x - 1 << ' ' << B.y + 1 << '\n';
// cerr << P1 << ' ' << P2 << '\n';
if(P1 != -1 && P2 != -1)
{
add_edge(P1, P2, B.x, B.y);
continue;
}
P1 = point_index(B.x + 1, B.y - 1);
P2 = point_index(B.x + 1, B.y + 1);
if(P1 != -1 && P2 != -1)
{
add_edge(P1, P2, B.x, B.y);
}
}
}
build(U, V, A, B);
return 1;
}
