#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
template <size_t N>
struct dsu
{
int64_t p[N];
dsu() { fill(p, p + N, -1); }
int64_t repr(int64_t u) { return p[u] < 0 ? u : p[u] = repr(p[u]); }
bool merge(int64_t i, int64_t j)
{
i = repr(i);
j = repr(j);
if (i == j)
return 0;
if (p[i] > p[j])
swap(i, j);
p[i] += p[j];
p[j] = i;
return 1;
}
bool same_set(int64_t i, int64_t j) { return repr(i) == repr(j); }
int64_t set_size(int64_t i) { return -p[repr(i)]; }
void reset() { fill(p.begin(), p.end(), -1); }
};
struct fountain
{
int x, y;
size_t i;
};
constexpr size_t N = 200000;
fountain f[N];
vector<pair<size_t, size_t>> edges;
vector<uint32_t> dual[N];
dsu<N> d;
set<pair<int, int>> points, marked;
set<tuple<int, int, uint32_t>> midpoints;
pair<int, int> dual_coords[N];
bitset<N> visited;
size_t l;
void mark_cut_points(uint32_t u)
{
visited[u] = 1;
for (auto const &v : dual[u])
if (!visited[v])
{
if (u == l)
{
bool placed = 0;
for (size_t i = 0; i < 4; ++i)
{
pair<int, int> cand = {dual_coords[v].first - 2 + (i & 1) * 4,
dual_coords[v].second - 2 + ((i & 2) >> 1) * 4};
bool not_present = 1;
for (auto const &w : dual[v])
if (w != u)
not_present &= dual_coords[w] != cand;
if (not_present)
{
marked.emplace((dual_coords[u].first + cand.first) >> 1,
(dual_coords[u].second + cand.second) >> 1);
placed = 1;
break;
}
}
assert(placed);
}
else
{
marked.emplace((dual_coords[u].first + dual_coords[v].first) >> 1,
(dual_coords[u].second + dual_coords[v].second) >> 1);
}
mark_cut_points(v);
}
}
int construct_roads(vector<int> x, vector<int> y)
{
size_t n = x.size();
for (size_t i = 0; i < n; ++i)
points.emplace(x[i], y[i]);
for (size_t i = 0; i < n; ++i)
if (points.find({x[i] + 2, y[i]}) != points.end() &&
points.find({x[i], y[i] + 2}) != points.end() &&
points.find({x[i] + 2, y[i] + 2}) != points.end())
midpoints.emplace(x[i] + 1, y[i] + 1, l++), dual_coords[l - 1] = {x[i] + 1, y[i] + 1};
for (auto const &[x, y, i] : midpoints)
{
auto it = midpoints.lower_bound({x + 2, y, 0});
if (it != midpoints.end() && get<0>(*it) == x + 2 && get<1>(*it) == y)
dual[i].push_back(get<2>(*it)), dual[get<2>(*it)].push_back(i);
it = midpoints.lower_bound({x, y + 2, 0});
if (it != midpoints.end() && get<0>(*it) == x && get<1>(*it) == y + 2)
dual[i].push_back(get<2>(*it)), dual[get<2>(*it)].push_back(i);
}
for (size_t i = 0; i < l; ++i)
if (dual[i].size() < 4)
dual[l].push_back(i), dual[i].push_back(l);
mark_cut_points(l);
for (size_t i = 0; i < x.size(); ++i)
f[i].i = i, f[i].x = x[i], f[i].y = y[i];
sort(f, f + n, [](auto const &a, auto const &b)
{ return a.y == b.y ? a.x < b.x : a.y < b.y; });
for (size_t i = 0; i < n;)
{
size_t j = i;
while (j < n && f[j].y == f[i].y)
++j;
for (size_t k = i + 1; k < j; ++k)
if (f[k - 1].x + 2 == f[k].x)
if (marked.find({f[k - 1].x + 1, f[k - 1].y}) == marked.end() &&
d.merge(f[k - 1].i, f[k].i))
edges.emplace_back(f[k - 1].i, f[k].i);
if (f[j].y == f[i].y + 2)
{
size_t k = j;
while (i < j && k < n && f[k].y == f[j].y)
{
if (f[i].x < f[k].x)
++i;
else if (f[k].x < f[i].x)
++k;
else
{
if (marked.find({f[i].x, f[i].y + 1}) == marked.end() &&
d.merge(f[i].i, f[k].i))
edges.emplace_back(f[k].i, f[i].i);
++i;
++k;
}
}
}
i = j;
}
if (d.set_size(0) != n)
return 0;
vector<int> u, v, a, b;
for (auto const &[i, j] : edges)
{
u.push_back(i);
v.push_back(j);
if (x[i] == x[j])
{
b.push_back((y[i] + y[j]) >> 1);
if (((x[i] & 3) == 2) ^ ((min(y[i], y[j]) & 3) == 2))
a.push_back(x[i] - 1);
else
a.push_back(x[i] + 1);
}
else
{
a.push_back((x[i] + x[j]) >> 1);
if (((y[i] & 3) == 2) ^ ((min(x[i], x[j]) & 3) == 2))
b.push_back(y[i] + 1);
else
b.push_back(y[i] - 1);
}
}
build(u, v, a, b);
return 1;
}
