#include "parks.h"
#include <map>
#include <algorithm>
#include <iostream>
const int MAX_N = 2e5;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int dxb[] = {-1, -1, 1, 1};
int dyb[] = {-1, 1, -1, 1};
bool used[1 + MAX_N];
std::map <std::pair <int, int>, int> fountains;
int nr;
void dfs (int node, std::vector <int> &x, std::vector <int> &y) {
used[node] = true;
++nr;
for (int dir = 0; dir < 4; dir++) {
int nx = x[node] + 2 * dx[dir];
int ny = y[node] + 2 * dy[dir];
if (fountains.count ({nx, ny})) {
int vec = fountains[{nx, ny}];
if (not used[vec])
dfs (vec, x, y);
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
std::vector<int> u, v, a, b;
int n = x.size ();
std::vector <std::pair <int, int>> bitches;
for (int i = 0; i < n; i++) {
fountains[{x[i], y[i]}] = i;
for (int dir = 0; dir < 4; dir++) {
int nx = x[i] + dxb[dir];
int ny = y[i] + dyb[dir];
bitches.push_back ({nx, ny});
}
}
nr = 0;
dfs (0, x, y);
if (nr < n)
return 0;
sort (bitches.begin (), bitches.end ());
bitches.resize (std::unique (bitches.begin (), bitches.end ()) - bitches.begin ());
for (std::pair <int, int> p : bitches) {
int color = (p.first / 2 + p.second / 2) % 2;
if (color == 0) {
/// <- or -> orizontal road
/// case 1 try from above
if (fountains.count({p.first - 1, p.second - 1}) && fountains.count ({p.first - 1, p.second + 1})) {
u.push_back (fountains[{p.first - 1, p.second - 1}]);
v.push_back (fountains[{p.first - 1, p.second + 1}]);
a.push_back (p.first);
b.push_back (p.second);
}
/// case 2 try from below
else if (fountains.count ({p.first + 1, p.second - 1}) && fountains.count ({p.first + 1, p.second + 1})) {
u.push_back (fountains[{p.first + 1, p.second - 1}]);
v.push_back (fountains[{p.first + 1, p.second + 1}]);
a.push_back (p.first);
b.push_back (p.second);
}
}
else {
/// v or ^ vertical road
/// case 1 try from the LHS
if (fountains.count({p.first - 1, p.second - 1}) && fountains.count ({p.first + 1, p.second - 1})) {
u.push_back (fountains[{p.first - 1, p.second - 1}]);
v.push_back (fountains[{p.first + 1, p.second - 1}]);
a.push_back (p.first);
b.push_back (p.second);
}
/// case 2 try from the RHS
else if (fountains.count ({p.first - 1, p.second + 1}) && fountains.count ({p.first + 1, p.second + 1})) {
u.push_back (fountains[{p.first - 1, p.second + 1}]);
v.push_back (fountains[{p.first + 1, p.second + 1}]);
a.push_back (p.first);
b.push_back (p.second);
}
}
}
build(u, v, a, b);
return 1;
}
/**
5
4 4
4 6
6 4
4 2
2 4
**/
