#include "parks.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) ((int)(x).size())
using namespace std;
typedef pair<int, int> ipair;
const ipair D[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
ipair operator + (ipair const& a, ipair const& b) { return {a.X+b.X, a.Y+b.Y}; }
ipair operator - (ipair const& a, ipair const& b) { return {a.X-b.X, a.Y-b.Y}; }
ipair operator * (ipair const& a, int b) { return {a.X*b, a.Y*b}; }
int construct_roads(std::vector<int> ix, std::vector<int> iy) {
int n = sz(ix);
map<ipair, int> fs;
set<pair<ipair, ipair>> roads;
for (int i = 0; i < n; ++i)
fs[{ix[i], iy[i]}] = i;
vector<int> ansA, ansB, ansX, ansY;
set<ipair> q;
set<ipair> vis;
set<ipair> done;
q.insert({ix[0], iy[0]});
vis.insert({ix[0], iy[0]});
bool isFirst = true;
while (!q.empty()) {
ipair p = *q.begin();
q.erase(p);
if (!isFirst) {
for (int i = 0; i < 4; ++i) {
ipair d = D[i];
ipair p2 = p + d * 2;
if (!done.count(p2)) continue;
ipair d2;
if ((p.X + p.Y) & 1) {
d2 = D[(i + 1) % 4];
} else {
d2 = D[(i + 3) % 4];
}
if (roads.count({p + d2 * 2, p2 + d2 * 2})) continue;
roads.insert({p, p2});
roads.insert({p2, p});
ansA.push_back(fs[p]);
ansB.push_back(fs[p2]);
ipair pp = p + d + d2;
ansX.push_back(pp.X);
ansY.push_back(pp.Y);
break;
}
}
isFirst = false;
done.insert(p);
for (auto d : D)
if (fs.count(p + d * 2) && !vis.count(p + d * 2)) {
q.insert(p + d * 2);
vis.insert(p + d * 2);
}
}
if (sz(vis) != n) return 0;
build(ansA, ansB, ansX, ansY);
return 1;
}
