#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<fountain> by_a;
vector<fountain> by_b;
vector<fountain> by_c;
bool sort_by_y(const fountain &a, const fountain &b) {
return a.y < b.y;
}
void solve() {
/*for(fountain p : points) {
if(p.x == 2) {
by_a.pb(p);
}
if(p.x == 4) {
by_b.pb(p);
}
if(p.x == 6) {
by_c.pb(p);
}
}
sort(by_a.begin(), by_a.end(), sort_by_y);
sort(by_b.begin(), by_b.end(), sort_by_y);
sort(by_c.begin(), by_c.end(), sort_by_y);*/
// type A and E
for(int i = 2; i <= maxn; i += 2) {
int a = fountain_at[2][i], b = fountain_at[2][i + 2];
if(a && b) {
build_road_bench(a - 1, b - 1, mp(1, i + 1));
}
a = fountain_at[6][i], b = fountain_at[6][i + 2];
if(a && b) {
build_road_bench(a - 1, b - 1, mp(7, i + 1));
}
}
// type B
for(int i = 2; i <= maxn; i += 2) {
int a = fountain_at[2][i], b = fountain_at[2][i + 2],
c = fountain_at[4][i], d = fountain_at[4][i + 2];
if((b && d) && (!a || !c)) {
build_road_bench(b - 1, d - 1, mp(3, i + 1));
}
}
// type C
for(int i = 2; i <= maxn; i += 2) {
int a = fountain_at[4][i], b = fountain_at[4][i + 2];
if(a && b) {
if(!bench_at[3][i + 1]) {
build_road_bench(a - 1, b - 1, mp(3, i + 1));
} else {
build_road_bench(a - 1, b - 1, mp(5, i + 1));
}
}
}
// type D
for(int i = 2; i <= maxn; i += 2) {
int a = fountain_at[4][i], b = fountain_at[4][i + 2],
c = fountain_at[6][i], d = fountain_at[6][i + 2];
if((b && d) && (!a || !c)) {
if(!bench_at[5][i + 1]) {
build_road_bench(b - 1, d - 1, mp(5, i + 1));
} else {
build_road_bench(b - 1, d - 1, mp(5, i + 3));
}
}
}
}
#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
*/
