#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<int> p, sz;
void init(int n) {
sz = vector<int>(n, 1);
p = vector<int>(n);
iota(p.begin(), p.end(), 0);
}
int find_set(int u) {
return u == p[u] ? u : p[u] = find_set(p[u]);
}
bool merge_set(int u, int v) {
u = find_set(u);
v = find_set(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
return true;
}
} dsu;
vector<int> x, y;
map<pair<int, int>, int> pos_idx;
map<pair<int, int>, int> edge_side;
set<pair<int, int>> vis;
set<pair<int, int>> bench_used;
vector<int> ret_u, ret_v, ret_a, ret_b;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void dfs(int u, int ent) {
int xu = x[u], yu = y[u];
for (int id = 0; id < 4; id++) {
int i = (ent+id+1)%4;
int xv = x[u] + 2*dx[i], yv = y[u] + 2*dy[i];
if (!pos_idx.count({xv, yv})) continue;
int v = pos_idx[{xv, yv}];
if (vis.count({u, v})) continue;
if (dsu.find_set(u) == dsu.find_set(v)) {
vis.insert({u, v});
dfs(v, i);
continue;
}
int bx, by;
if (dx[i] == 1) {
bx = xu + dx[i];
by = yu + 1;
} else if (dx[i] == -1) {
bx = xu + dx[i];
by = yu - 1;
} else if (dy[i] == 1) {
bx = xu - 1;
by = yu + dy[i];
} else if (dy[i] == -1) {
bx = xu + 1;
by = yu + dy[i];
}
if (!bench_used.count({bx, by})) {
ret_u.push_back(u);
ret_v.push_back(v);
ret_a.push_back(bx);
ret_b.push_back(by);
bench_used.insert({bx, by});
dsu.merge_set(u, v);
}
vis.insert({u, v});
dfs(v, i);
}
}
int construct_roads(vector<int> _x, vector<int> _y) {
x = _x; y = _y;
int n = x.size();
dsu.init(n);
for (int i = 0; i < n; i++) pos_idx[{x[i], y[i]}] = i;
int start = 0;
for (int i = 0; i < n; i++) {
if (make_pair(y[i], -x[i]) > make_pair(y[start], -x[start])) start = i;
}
dfs(start, 0);
// Check connectivity
vector<vector<int>> edge_used(n, vector<int>());
for (int i = 0; i < ret_u.size(); i++) {
edge_used[ret_u[i]].push_back(ret_v[i]);
edge_used[ret_v[i]].push_back(ret_u[i]);
}
vector<bool> visited(n);
queue<int> bfs;
bfs.push(0);
while (!bfs.empty()) {
int u = bfs.front();
bfs.pop();
if (visited[u]) continue;
visited[u] = true;
for (int v : edge_used[u]) bfs.push(v);
}
for (int i = 0; i < n; i++) if (!visited[i]) return 0;
build(ret_u, ret_v, ret_a, ret_b);
return 1;
}
