#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
const int mxN = 2e5 + 1;
const int dx[mxN] = {0, 1, 0, -1}, dy[mxN] = {1, 0, -1, 0};
bool vis[mxN];
pair<pii, int> pts[mxN];
pii opts[mxN];
map<pii, int> allpts;
int n;
bool CheckConnected() {
queue<pii> q;
set<pii> track;
q.push(pts[0].ff);
track.insert(pts[0].ff);
while (!q.empty()) {
pii cur = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = cur.ff + dx[k] * 2;
int ny = cur.ss + dy[k] * 2;
if (allpts.find({nx, ny}) != allpts.end() && track.find({nx, ny}) == track.end()) {
q.push({nx, ny});
track.insert({nx, ny});
}
}
}
return (int(track.size()) == n);
}
bool sortx(pair<pii, int> a, pair<pii, int> b) {
if (a.ff.ss != b.ff.ss) return a.ff.ss < b.ff.ss;
return a.ff.ff < b.ff.ff;
}
bool sorty(pair<pii, int> a, pair<pii, int> b) {
if (a.ff.ff != b.ff.ff) return a.ff.ff < b.ff.ff;
return a.ff.ss < b.ff.ss;
}
void st12() {
sort(pts, pts + n, sorty);
vector<pii> edge;
vis[pts[0].ss] = true;
for (int i = 0; i < n; i++) {
if (allpts.find({pts[i].ff.ff, pts[i].ff.ss + 2}) != allpts.end()) {
int v = allpts[{pts[i].ff.ff, pts[i].ff.ss + 2}];
if (!vis[v]) {
edge.pb({pts[i].ss, v});
vis[v] = true;
}
}
if (pts[i].ff.ff == 4 && allpts.find({2, pts[i].ff.ss}) != allpts.end()) {
int v = allpts[{2, pts[i].ff.ss}];
if (!vis[pts[i].ss] || !vis[v]) {
edge.pb({pts[i].ss, v});
vis[pts[i].ss] = true;
vis[v] = true;
}
}
}
int m = edge.size();
vector<int> u(m), v(m), a(m), b(m);
for (int i = 0; i < m; i++) {
u[i] = edge[i].ff;
v[i] = edge[i].ss;
if (opts[u[i]].ff == opts[v[i]].ff) {
a[i] = (opts[u[i]].ff == 2 ? 1 : 5);
b[i] = ((opts[u[i]].ss + opts[v[i]].ss) >> 1);
} else {
a[i] = 3;
b[i] = opts[u[i]].ss - 1;
}
}
build(u, v, a, b);
return;
}
void st3() {
int arr[3][mxN + 10];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < mxN + 10; j++) {
arr[i][j] = -1;
}
}
for (int i = 0; i < n; i++) {
arr[(pts[i].ff.ff >> 1) - 1][pts[i].ff.ss] = pts[i].ss;
}
bool con01 = false, con12 = false;
bool notfix = false;
vector<int> u, v, a, b;
for (int i = 0; i < mxN; i += 2) {
// if (i <= 10) cout << arr[0][i] << ' ' << arr[1][i] << ' ' << arr[2][i] << endl;
if (arr[0][i] >= 0 && arr[0][i + 2] >= 0) {
u.pb(arr[0][i]); v.pb(arr[0][i + 2]);
a.pb(1); b.pb(i + 1);
}
if (arr[2][i] >= 0 && arr[2][i + 2] >= 0) {
u.pb(arr[2][i]); v.pb(arr[2][i + 2]);
a.pb(7); b.pb(i + 1);
}
bool special = false;
if (notfix) {
u.pb(arr[0][i]); v.pb(arr[1][i]);
a.pb(3); b.pb(i + 1);
special = true;
notfix = false;
}
bool usemid = false;
if (arr[1][i] >= 0 && arr[1][i + 2] >= 0) {
u.pb(arr[1][i]); v.pb(arr[1][i + 2]);
a.pb((special ? 5 : 3)); b.pb(i + 1);
usemid = true;
}
if (arr[0][i + 2] >= 0 && arr[1][i + 2] >= 0 && !con01) {
if (!usemid) {
u.pb(arr[0][i + 2]); v.pb(arr[1][i + 2]);
a.pb(3); b.pb(i + 1);
} else notfix = true;
con01 = true;
} else con01 = false;
if (arr[1][i + 2] >= 0 && arr[2][i + 2] >= 0 && !con12) {
u.pb(arr[1][i + 2]); v.pb(arr[2][i + 2]);
a.pb(5); b.pb(i + 1);
con12 = true;
} else con12 = false;
}
build(u, v, a, b);
return;
}
int construct_roads(vector<int> ox, vector<int> oy) {
n = ox.size();
int maxx = 0;
for (int i = 0; i < n; i++) {
pts[i] = {{ox[i], oy[i]}, i};
opts[i] = pts[i].ff;
allpts[pts[i].ff] = i;
maxx = max(maxx, pts[i].ff.ff);
}
// for (int i = 0; i < n; i++) {
// cout << pts[i].ff.ff << ' ' << pts[i].ff.ss << ' ' << pts[i].ss << endl;
// }
if (!CheckConnected()) return 0;
if (maxx == 2 || maxx == 4) st12();
else if (maxx == 6) st3();
return 1;
}
