#include "parks.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 200'010;
namespace dsu {
int par[N];
void init(int n) { memset(par, -1, sizeof(*par)*n); }
int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
bool unite(int v, int u) {
v = rt(v);
u = rt(u);
if (v == u)
return 0;
par[u] = v;
return 1;
}
}
map<pii,int> pts;
vector<pii> edge;
vector<int> X, Y;
int n;
int get_pnt(int x, int y)
{
auto it = pts.find(pii(x, y));
return it == pts.end()? -1: it->second;
}
tuple<int,int,int,int> get_chair(int p1, int p2)
{
int x1 = X[p1], y1 = Y[p1], x2 = X[p2], y2 = Y[p2];
if (x1 == x2)
return {x1-1, (y1+y2)/2, x1+1, (y1+y2)/2};
else
return {(x1+x2)/2, y1-1, (x1+x2)/2, y1+1};
}
namespace matching {
int match[3*N];
int par[3*N];
vector<int> A[3*N];
vector<pii> chairs;
bool bfs(int s)
{
vector<int> q = {s}, q2;
par[s] = -2;
int vv;
Loop (i,0,q.size()) {
int v = q[i];
//cerr << "bfs " << v << '\n';
for (int u : A[v]) {
if (par[u] != -1)
continue;
par[u] = v;
q2.push_back(u);
if (match[u] == -1) {
vv = u;
goto found;
}
int u2 = match[u];
par[u2] = u;
q.push_back(u2);
}
}
return 0;
found:
while (vv != -2) {
match[vv] = par[vv];
match[par[vv]] = vv;
vv = par[par[vv]];
}
for (int x : q2)
par[x] = -1;
return 1;
}
vector<pii> get_match(vector<pii> e) {
int m = e.size();
chairs.clear();
Loop (i,0,m) {
auto [p1, p2] = e[i];
auto [x1, y1, x2, y2] = get_chair(p1, p2);
chairs.emplace_back(x1, y1);
chairs.emplace_back(x2, y2);
}
sort(chairs.begin(), chairs.end());
chairs.resize(unique(chairs.begin(), chairs.end()) - chairs.begin());
//for (auto [x, y] : chairs)
// cerr << x << ' ' << y << '\n';
Loop (i,0,m+chairs.size()) {
A[i].clear();
match[i] = -1;
par[i] = -1;
}
Loop (i,0,m) {
auto [p1, p2] = e[i];
auto [x1, y1, x2, y2] = get_chair(p1, p2);
int c1 = lower_bound(chairs.begin(), chairs.end(), pii(x1, y1)) - chairs.begin();
int c2 = lower_bound(chairs.begin(), chairs.end(), pii(x2, y2)) - chairs.begin();
A[i].push_back(m+c1);
A[i].push_back(m+c2);
A[m+c1].push_back(i);
A[m+c2].push_back(i);
}
Loop (i,0,m) {
//cerr << "try " << i << '\n';
if (!bfs(i))
return {};
//Loop (i,0,m+chairs.size())
// cerr << match[i] << ' ';
//cerr << '\n';
}
//cerr << "all good!\n";
vector<pii> ans;
Loop (i,0,m) {
int c = match[i]-m;
ans.emplace_back(chairs[c].first, chairs[c].second);
}
return ans;
}
}
void make_edges()
{
Loop (i,0,n) {
int x = X[i];
int y = Y[i];
int p1 = get_pnt(x, y+2);
if (p1 != -1)
edge.push_back({i, p1});
}
Loop (i,0,n) {
int x = X[i];
int y = Y[i];
int p1 = get_pnt(x+2, y);
if (p1 != -1)
edge.push_back({i, p1});
}
}
namespace dfs {
vector<int> A[N];
bool vis[N];
vector<pii> ans;
void dfs(int v) {
vis[v] = 1;
for (int u : A[v]) {
if (vis[u])
continue;
ans.emplace_back(v, u);
dfs(u);
}
}
vector<pii> Do(int n, int s, vector<pii> e) {
Loop (i,0,n) {
A[i].clear();
vis[i] = 0;
}
ans.clear();
for (auto [x, y] : e) {
A[x].push_back(y);
A[y].push_back(x);
}
dfs(0);
return ans;
}
}
int construct_roads(std::vector<int> _X, std::vector<int> _Y) {
X = _X; Y = _Y;
n = X.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
Loop (i,0,n)
pts[pii(X[i], Y[i])] = i;
make_edges();
//for (auto [x, y] : edge)
// cerr << X[x] << ' ' << Y[x] << " - " << X[y] << ' ' << Y[y] << '\n';
mt19937_64 rd(time(0));
while (clock() < 3*CLOCKS_PER_SEC) {
dsu::init(n);
vector<pii> e = dfs::Do(n, rd()%n, edge);
if (e.size() != n-1)
return 0;
auto chairs = matching::get_match(e);
//cerr << "found!\n";
//for (auto [x, y] : chairs)
// cerr << x << ' ' << y << '\n';
if (chairs.empty()) {
shuffle(edge.begin(), edge.end(), rd);
continue;
}
vector<int> ex, ey, cx, cy;
Loop (i,0,n-1) {
ex.push_back(e[i].first);
ey.push_back(e[i].second);
cx.push_back(chairs[i].first);
cy.push_back(chairs[i].second);
}
build(ex, ey, cx, cy);
return 1;
}
return 0;
}
