#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;
unordered_map<int, unordered_map<int, bool> > road_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;
road_at[(points[road_u].x + points[road_v].x) / 2][(points[road_u].y + points[road_v].y) / 2] = true;
}
vector<pii> get_bench_locations_pii(pii a, pii b) {
fountain f_a = fountain(a.fi, a.se, -1), f_b = fountain(b.fi, b.se, -1);
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)};
}
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)};
}
int get_middle_of_intersection(int a_idx, int b_idx) {
pii a = mp(points[a_idx].x, points[a_idx].y);
pii b = mp(points[b_idx].x, points[b_idx].y);
int cnt = 0;
for(pii dir : directions) {
pii nei = mp(a.fi + dir.fi, a.se + dir.se);
if(fountain_at[nei.fi][nei.se]) {
cnt++;
}
}
if(cnt == 4) {
return a_idx;
}
cnt = 0;
for(pii dir : directions) {
pii nei = mp(b.fi + dir.fi, b.se + dir.se);
if(fountain_at[nei.fi][nei.se]) {
cnt++;
}
}
if(cnt == 4) {
return b_idx;
}
return -1;
}
pii get_bench_when_in_intersection(int a_idx, int b_idx) {
// a is the middle, b is a neighbour
fountain a = points[a_idx], b = points[b_idx];
if(b.x < a.x) {
return mp(a.x - 1, a.y + 1);
}
if(b.y < a.y) {
return mp(a.x - 1, a.y - 1);
}
if(b.y > a.y) {
return mp(a.x + 1, a.y + 1);
}
if(b.x > a.x) {
return mp(a.x + 1, a.y - 1);
}
}
pii orig;
unordered_map<int, unordered_map<int, int> > not_bad;
bool bad_bench(pii bench, pii a, pii b) {
int tmp = not_bad[bench.fi][bench.se];
if(tmp == 1) {
return false;
}
if(tmp == 2) {
return true;
}
if(a > b) {
swap(a, b);
}
vector<pii > v = {a, b};
for(pii dir : directions) {
pii other = mp(bench.fi + dir.fi, bench.se + dir.se);
vector<pii> corners = get_bench_locations_pii(bench, other);
if(corners != v) {
if(fountain_at[corners[0].fi][corners[0].se] &&
fountain_at[corners[1].fi][corners[1].se] &&
//bench_at[other.fi][other.se] &&
!road_at[(bench.fi + other.fi) / 2][(bench.se + other.se) / 2]) {
if(other == orig) {
not_bad[bench.fi][bench.se] = 1;
return false;
}
if(bench_at[other.fi][other.se]) {
//not_bad[bench.fi][bench.se] = 2;
return true;
} else {
bool res = bad_bench(other, corners[0], corners[1]);
if(res) {
//not_bad[bench.fi][bench.se] = 2;
} else {
not_bad[bench.fi][bench.se] = 1;
}
return res;
}
}
}
}
not_bad[bench.fi][bench.se] = 1;
return false;
}
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);
int mid = get_middle_of_intersection(cur, new_id);
if(mid != -1) {
build_road_bench(cur, new_id, get_bench_when_in_intersection(mid, cur ^ new_id ^ mid));
} else {
vector<pii> benches = get_bench_locations(cur, new_id);
orig = benches[0];
if(!bench_at[benches[0].fi][benches[0].se] && !bad_bench(benches[0], mp(points[cur].x, points[cur].y), mp(points[new_id].x, points[new_id].y))) {
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
*/
