/* Ignut
started: 16.08.2024
now: 16.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
struct DSU {
int cntComp;
vector<int> p, sz;
void Init(int n) {
cntComp = n;
p.assign(n, 0);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
int Get(int v) {
return p[v] == v ? v : p[v] = Get(p[v]);
}
void Unite(int u, int v) {
u = Get(u), v = Get(v);
if (u == v) return;
cntComp --;
if (sz[u] > sz[v]) swap(u, v);
p[u] = v;
sz[v] += sz[u];
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i ++) mp[{x[i], y[i]}] = i + 1;
DSU dsu; dsu.Init(n);
vector<int> u, v, a, b;
map<tuple<int, int, int, int>, int> have;
auto MakeEdge = [&u, &v, &dsu, &x, &y, &have](int i, int j) -> void {
u.push_back(i);
v.push_back(j);
dsu.Unite(i, j);
have[{x[i], y[i], x[j], y[j]}] ++;
have[{x[j], y[j], x[i], y[j]}] ++;
};
for (int i = 0; i < n; i ++) {
if (mp.count({x[i] + 2, y[i]})) {
int j = mp[{x[i] + 2, y[i]}] - 1;
if (dsu.Get(i) != dsu.Get(j))
MakeEdge(i, j);
}
if (mp.count({x[i], y[i] + 2})) {
int j = mp[{x[i], y[i] + 2}] - 1;
if (dsu.Get(i) != dsu.Get(j))
MakeEdge(i, j);
}
}
if (dsu.cntComp > 1) return 0;
a.assign(n - 1, 0), b.assign(n - 1, 0);
map<tuple<int, int, int, int>, pair<int, int>> res;
for (int i = 0; i < u.size(); i ++) {
if (res.count({x[u[i]], y[u[i]], x[v[i]], y[v[i]]})) {
auto [xx, yy] = res[{x[u[i]], y[u[i]], x[v[i]], y[v[i]]}];
a[i] = xx, b[i] = yy;
continue;
}
if (res.count({x[v[i]], y[v[i]], x[u[i]], y[u[i]]})) {
auto [xx, yy] = res[{x[v[i]], y[v[i]], x[u[i]], y[u[i]]}];
a[i] = xx, b[i] = yy;
continue;
}
int x1 = x[u[i]], y1 = y[u[i]], x2 = x[v[i]], y2 = y[v[i]];
int xf, yf;
if (x1 == x2) xf = x1 - 1;
else xf = (x1 + x2) / 2;
if (y1 == y2) yf = y1 - 1;
else yf = (y1 + y2) / 2;
a[i] = xf, b[i] = yf;
auto Try = [&x1, &y1, &x2, &y2, &xf, &yf, &have, &res](int xx1, int yy1, int xx2, int yy2, int dxf, int dyf) -> bool {
if (res.count({xx1, yy1, xx2, yy2})) return false;
if (res.count({xx2, yy2, xx1, yy1})) return false;
if (have.count({xx1, yy1, xx2, yy2})) {
x1 = xx1, y1 = yy1, x2 = xx2, y2 = yy2;
xf += dxf;
yf += dyf;
return true;
}
return false;
};
while (true) {
res[{x1, y1, x2, y2}] = {xf, yf};
if (x1 == x2) {
if (xf < x1) {
if (Try(x1 - 2, y2, x1, y2, 0, +2)) continue;
if (Try(x1 - 2, y1, x1 - 2, y2, -2, 0)) continue;
if (Try(x1 - 2, y1, x1, y1, 0, -2)) continue;
}
else {
if (Try(x1, y2, x1 + 2, y2, 0, +2)) continue;
if (Try(x1 + 2, y1, x1 + 1, y2, +2, 0)) continue;
if (Try(x1, y1, x1 + 2, y1, 0, -2)) continue;
}
}
else {
if (yf > y1) {
if (Try(x1, y1, x1, y1 + 2, -2, 0)) continue;
if (Try(x1, y1 + 2, x2, y1 + 2, 0, +2)) continue;
if (Try(x2, y2, x2, y2 + 2, +2, 0)) continue;
}
else {
if (Try(x1, y1 - 2, x1, y1, -2, 0)) continue;
if (Try(x1, y1 - 2, x2, y1 - 2, 0, -2)) continue;
if (Try(x2, y1 - 2, x2, y2, +2, 0)) continue;
}
}
break;
}
}
build(u, v, a, b);
return 1;
}
