#include "parks.h"
#include <map>
#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int uf[200006];
int _find(int x) {
if (uf[x] == -1) return x;
return uf[x] = _find(uf[x]);
}
void _merge(int x, int y) {
x = _find(x), y = _find(y);
if (x != y) uf[x] = y;
}
map<pair<int, int>, int> m;
set<pair<int, int>> s;
int construct_roads(vector<int> x, vector<int> y) {
if ((int)x.size() == 1) return build({}, {}, {}, {}), 1;
int n = (int)x.size();
for (int i = 0; i < n; i++) uf[i] = -1;
vector<int> u, v, a, b;
vector<pair<int, int>> edges, n_edges;
vector<int> points;
for (int i = 0; i < n; i++) m[{ x[i], y[i] }] = i;
for (int i = 0; i < n; i++) if (m.count({ x[i], y[i] - 2 })) {
edges.push_back({ m[{ x[i], y[i] - 2 }], i });
_merge(edges.back().first, edges.back().second);
}
for (int i = 0; i < n; i++) if (!m.count({ x[i], y[i] - 2 }) || !m.count({ x[i], y[i] + 2 })) points.push_back(i);
sort(points.begin(), points.end(), [&](const int &a, const int &b) {
if (y[a] != y[b]) return y[a] < y[b];
return x[a] < x[b];
});
for (int t = 0; t < (int)points.size(); t++) {
int i = points[t];
if (m.count({ x[i] - 2, y[i] })) {
int t = m[{ x[i] - 2, y[i] }];
if (_find(t) != _find(i)) {
edges.push_back({ t, i });
_merge(t, i);
}
}
}
for (int i = 1; i < n; i++) if (_find(0) != _find(i)) return 0;
//int min_x = *min_element(x.begin(), x.end()), max_x = *max_element(x.begin(), x.end());
for (auto &i: edges) {
/*if (x[i.first] == x[i.second]) {
u.push_back(i.first);
v.push_back(i.second);
a.push_back(x[i.first] - 1);
b.push_back((y[i.first] + y[i.second]) / 2);
s.insert({ a.back(), b.back() });
} else*/ n_edges.push_back(i);
}
sort(n_edges.begin(), n_edges.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
if (x[a.first] + x[a.second] != x[b.first] + x[b.second]) return x[a.first] + x[a.second] < x[b.first] + x[b.second];
return y[a.first] + y[a.second] < y[b.first] + y[b.second];
});
for (auto &i: n_edges) {
if (x[i.first] == x[i.second]) {
if (!s.count({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 })) {
s.insert({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back(x[i.first] - 1);
b.push_back((y[i.first] + y[i.second]) / 2);
} else {
if (s.count({ x[i.first] + 1, (y[i.first] + y[i.second]) / 2 })) return 0;
s.insert({ x[i.first] + 1, (y[i.first] + y[i.second]) / 2 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back(x[i.first] + 1);
b.push_back((y[i.first] + y[i.second]) / 2);
}
} else {
if (!s.count({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 })) {
s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back((x[i.first] + x[i.second]) / 2);
b.push_back(y[i.first] - 1);
} else {
if (s.count({ (x[i.first] + x[i.second]) / 2, y[i.first] + 1 })) return 0;
s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] + 1 });
u.push_back(i.first);
v.push_back(i.second);
a.push_back((x[i.first] + x[i.second]) / 2);
b.push_back(y[i.first] + 1);
}
}
}
build(u, v, a, b);
return 1;
}
