#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define x X
#define y Y
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 2e5;
const vector<pii > directions = {mp(-2, 0), mp(0, -2), mp(0, 2), mp(2, 0)};
bool check_possibility(int n, vector<int> x, vector<int> y) {
unordered_map<int, unordered_map<int, bool> > m;
unordered_map<int, unordered_map<int, int> > f;
for(int i = 0; i < n; i++) {
f[x[i]][y[i]] = i + 1;
}
queue<int> q;
q.push(0);
m[x[0]][y[0]] = true;
int cnt = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
cnt++;
for(pii dir : directions) {
pii new_point = mp(x[cur] + dir.fi, y[cur] + dir.se);
if(f[new_point.fi][new_point.se] && !m[new_point.fi][new_point.se]) {
m[new_point.fi][new_point.se] = true;
int new_id = f[new_point.fi][new_point.se] - 1;
q.push(new_id);
}
}
}
return (cnt == n);
}
struct fountain {
int x, y, id;
fountain() : x(0), y(0), id(-1) {}
fountain(int x_, int y_, int id_) :
x(x_), y(y_), id(id_) {}
};
int n;
vector<fountain > points;
vector<int> x;
vector<int> y;
unordered_map<int, unordered_map<int, int> > fountain_at;
unordered_map<int, unordered_map<int, bool> > bench_at;
vector<int> ans_u;
vector<int> ans_v;
vector<int> ans_a;
vector<int> ans_b;
void build_road_bench(int road_u, int road_v, pii bench_pos) {
ans_u.pb(road_u);
ans_v.pb(road_v);
ans_a.pb(bench_pos.fi);
ans_b.pb(bench_pos.se);
bench_at[bench_pos.fi][bench_pos.se] = true;
}
vector<pii> get_bench_locations(int a_idx, int b_idx) {
fountain f_a = points[a_idx], f_b = points[b_idx];
pii a, b;
if(f_a.x == f_b.x) {
int new_y = (f_a.y + f_b.y) / 2;
a = mp(f_a.x + 1, new_y), b = mp(f_a.x - 1, new_y);
} else {
int new_x = (f_a.x + f_b.x) / 2;
a = mp(new_x, f_a.y + 1), b = mp(new_x, f_a.y - 1);
}
return {min(a, b), max(a, b)};
}
void solve() {
unordered_map<int, unordered_map<int, bool> > vis;
queue<int> q;
q.push(0);
vis[x[0]][y[0]] = true;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(pii dir : directions) {
pii new_point = mp(x[cur] + dir.fi, y[cur] + dir.se);
if(fountain_at[new_point.fi][new_point.se] && !vis[new_point.fi][new_point.se]) {
vis[new_point.fi][new_point.se] = true;
int new_id = fountain_at[new_point.fi][new_point.se] - 1;
q.push(new_id);
vector<pii> benches = get_bench_locations(cur, new_id);
if(!bench_at[benches[0].fi][benches[0].se]) {
build_road_bench(cur, new_id, benches[0]);
} else {
build_road_bench(cur, new_id, benches[1]);
}
}
}
}
//
}
#undef x
#undef y
int construct_roads(vector<int> x, vector<int> y) {
// edge case
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
// sample solution
/*vector<int> u, v, a, b;
u.push_back(0);
v.push_back(1);
a.push_back(x[0]+1);
b.push_back(y[0]-1);
build(u, v, a, b);*/
n = x.size();
if(!check_possibility(n, x, y)) {
return 0;
}
X = x;
Y = y;
points.assign(n, fountain());
for(int i = 0; i < n; i++) {
points[i] = fountain(x[i], y[i], i);
fountain_at[x[i]][y[i]] = i + 1;
}
solve();
// build solution
build(ans_u, ans_v, ans_a, ans_b);
return 1;
}
/*
5
4 4
4 6
6 4
4 2
2 4
*/
