#include "parks.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <utility>
using namespace std;
int n;
int uf[200005];
map<pair<int, int>, int> pt2idx;
int fin(int x)
{
if (uf[x] == x) return x;
return uf[x] = fin(uf[x]);
}
void un(int x, int y)
{
x = fin(x);
y = fin(y);
if (x != y) uf[x] = y;
}
vector<int> ansu, ansv, ansa, ansb;
bool build_edge(int x1, int y1, int x2, int y2, int bx, int by)
{
int p1 = pt2idx[make_pair(x1, y1)];
int p2 = pt2idx[make_pair(x2, y2)];
if (fin(p1) == fin(p2)) return false;
un(p1, p2);
ansu.push_back(p1);
ansv.push_back(p2);
ansa.push_back(bx);
ansb.push_back(by);
return true;
}
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
for (int i = 0; i < n; i++) uf[i] = i;
set<pair<int, int> > st, bench;
for (int i = 0; i < n; i++) {
st.insert(make_pair(x[i], y[i]));
pt2idx[make_pair(x[i], y[i])] = i;
bench.insert(make_pair(x[i]-1, y[i]-1));
bench.insert(make_pair(x[i]-1, y[i]+1));
bench.insert(make_pair(x[i]+1, y[i]-1));
bench.insert(make_pair(x[i]+1, y[i]+1));
}
while (!bench.empty()) {
pair<int, int> cur = *(bench.begin());
bench.erase(bench.begin());
if ((cur.first + cur.second) % 4 == 0) {
if (st.count(make_pair(cur.first - 1, cur.second - 1)) &&
st.count(make_pair(cur.first + 1, cur.second - 1))) {
if (build_edge(cur.first - 1, cur.second - 1,
cur.first + 1, cur.second - 1, cur.first, cur.second)) continue;
}
if (st.count(make_pair(cur.first - 1, cur.second + 1)) &&
st.count(make_pair(cur.first + 1, cur.second + 1))) {
build_edge(cur.first - 1, cur.second + 1,
cur.first + 1, cur.second + 1, cur.first, cur.second);
}
} else {
if (st.count(make_pair(cur.first - 1, cur.second - 1)) &&
st.count(make_pair(cur.first - 1, cur.second + 1))) {
if (build_edge(cur.first - 1, cur.second - 1,
cur.first - 1, cur.second + 1, cur.first, cur.second)) continue;
}
if (st.count(make_pair(cur.first + 1, cur.second - 1)) &&
st.count(make_pair(cur.first + 1, cur.second + 1))) {
build_edge(cur.first + 1, cur.second - 1,
cur.first + 1, cur.second + 1, cur.first, cur.second);
}
}
}
if (ansa.size() < n - 1) {
return 0;
}
build(ansu, ansv, ansa, ansb);
return 1;
}
