#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct DisjointSet {
int n;
vector<int> parent, rank;
DisjointSet(int _n) : n(_n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
rank.resize(n, 0);
}
int find(int u) {
return parent[u] = (u == parent[u] ? u : find(parent[u]));
}
void merge(int u, int v) {
u = find(u); v = find(v);
if (u == v) return;
if (rank[u] > rank[v]) swap(u, v);
parent[u] = v;
if (rank[u] == rank[v]) ++rank[v];
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
map<pii, int> fountains;
for (int i=0; i<n; ++i) fountains[{ x[i], y[i] }] = i;
set<pii> bench_cands;
set<pii> road_cands; // store midpoint of adjacent fountains
DisjointSet dsu(n);
vector<vector<int>> points(200001);
for (int i=0; i<n; ++i) points[x[i]].push_back(y[i]);
for (auto& v: points) sort(v.begin(), v.end());
for (int x=2; x<points.size(); x+=2) {
for (int j=0; j<points[x].size(); ++j) {
int y = points[x][j];
if (fountains.count({ x-2, y })) {
bench_cands.insert({ x-1, y-1 });
bench_cands.insert({ x-1, y+1 });
road_cands.insert({ x-1, y });
dsu.merge(fountains[{ x-2, y }], fountains[{ x, y }]);
}
if (j+1 < points[x].size() && points[x][j+1] == y+2) {
bench_cands.insert({ x-1, y+1 });
bench_cands.insert({ x+1, y+1 });
road_cands.insert({ x, y+1 });
dsu.merge(fountains[{ x, y }], fountains[{ x, y+2 }]);
}
}
}
for (int i=1; i<n; ++i) {
if (dsu.find(i) != dsu.find(0)) {
return 0;
}
}
vector<int> U, V, A, B;
for (auto[a, b]: bench_cands) {
bool is_black = ((a+b) % 4 == 2);
if (is_black) {
if (road_cands.count({ a, b+1 })) {
U.push_back(fountains[{ a-1, b+1 }]);
V.push_back(fountains[{ a+1, b+1 }]);
A.push_back(a);
B.push_back(b);
road_cands.erase({ a, b+1 });
} else if (road_cands.count({ a, b-1 })) {
U.push_back(fountains[{ a-1, b-1 }]);
V.push_back(fountains[{ a+1, b-1 }]);
A.push_back(a);
B.push_back(b);
road_cands.erase({ a, b-1 });
}
} else {
if (road_cands.count({ a-1, b })) {
U.push_back(fountains[{ a-1, b-1 }]);
V.push_back(fountains[{ a-1, b+1 }]);
A.push_back(a);
B.push_back(b);
road_cands.erase({ a-1, b });
} else if (road_cands.count({ a+1, b })) {
U.push_back(fountains[{ a+1, b-1 }]);
V.push_back(fountains[{ a+1, b+1 }]);
A.push_back(a);
B.push_back(b);
road_cands.erase({ a+1, b });
}
}
}
build(U, V, A, B);
return 1;
}
