#include "parks.h"
#include <iostream>
#include <numeric>
#include <algorithm>
#include <utility>
#include <map>
#include <cassert>
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
struct Dsu {
vector<int> rnk, par;
Dsu(int n) : rnk(n, 1), par(n) {
iota(par.begin(), par.end(), 0);
}
int root(int v) {
return v == par[v] ? v : par[v] = root(par[v]);
}
bool same(int a, int b) {
return root(a) == root(b);
}
bool unite(int a, int b) {
a = root(a), b = root(b);
if (a == b) {
return false;
} else {
if (rnk[a] < rnk[b]) swap(a, b);
rnk[a] += rnk[b];
par[b] = a;
return true;
}
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
const int n = x.size();
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
return make_pair(x[i], y[i]) < make_pair(x[j], y[j]);
});
map<pi, int> ord;
for (int i = 0; i < n; ++i) {
ord[{x[i], y[i]}] = i;
}
Dsu dsu(n);
vi u, v, a, b;
int edges = 0;
auto get_id = [&](int x, int y) {
if (!ord.count({x, y})) return -1;
return ord[{x, y}];
};
auto get_chair = [&] (int x1, int y1, int x2, int y2) {
if ((x1 + y1) % 4) swap(x1, x2), swap(y1, y2);
const int x3 = x1 - (y2 - y1);
const int y3 = y1 + (x2 - x1);
return pi {(x2+x3)>>1, (y2+y3)>>1};
};
auto add_edge = [&](int x1, int y1, int x2, int y2) {
if (!ord.count({x1, y1}) || !ord.count({x2, y2})) return;
const int i = ord[{x1, y1}];
const int j = ord[{x2, y2}];
const auto [cx, cy] = get_chair(x1, y1, x2, y2);
if (dsu.unite(i, j)) {
u.push_back(i);
v.push_back(j);
a.push_back(cx);
b.push_back(cy);
edges++;
}
};
for (int i : p) {
const int px = x[i], py = y[i];
if (get_id(px-2, py-2) != -1 && get_id(px-2, py) != -1 && get_id(px, py-2) != -1) {
const auto [nx, ny] = get_chair(px, py, px-2, py);
if (nx != px - 1 || ny != py - 1) {
add_edge(px, py, px-2, py);
} else {
add_edge(px, py, px, py-2);
}
} else {
add_edge(px, py, px, py-2);
add_edge(px, py, px-2, py);
}
}
if (edges == n - 1) {
build(u, v, a, b);
return 1;
} else {
return 0;
}
}
