#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;
vector<pii> edges;
vector<pii> imp;
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});
edges.pb({allpts[cur], allpts[{nx, ny}]});
}
}
}
return (int(track.size()) == n);
}
void st123() {
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 + 6; 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 + 2] >= 0 && arr[2][i + 2] >= 0 && !con12)) special = true;
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 = !special;
}
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;
}
void st45() {
set<pair<pii, pii> > edgeset;
for (pii &cur : edges) {
pair<pii, pii> edge = {opts[cur.ff], opts[cur.ss]};
if (edge.ff.ff > edge.ss.ff) {
swap(edge.ff, edge.ss);
swap(cur.ff, cur.ss);
} else if (edge.ff.ff == edge.ss.ff && edge.ff.ss > edge.ss.ss) {
swap(edge.ff, edge.ss);
swap(cur.ff, cur.ss);
}
edgeset.insert(edge);
}
vector<int> ordering[4];
for (int i = 0; i < edges.size(); i++) {
pii fir = opts[edges[i].ff], sec = opts[edges[i].ss];
pii important;
bool left, right, middle;
if (fir.ff == sec.ff) {
// -2
left = (edgeset.find({{fir.ff - 2, fir.ss}, fir}) != edgeset.end());
right = (edgeset.find({{sec.ff - 2, sec.ss}, sec}) != edgeset.end());
middle = (edgeset.find({{fir.ff - 2, fir.ss}, {sec.ff - 2, sec.ss}}) != edgeset.end());
if (left && right) important.ff = 3;
else if (middle) important.ff = 2;
else if (left || right) important.ff = 1;
else important.ff = 0;
// +2
left = (edgeset.find({fir, {fir.ff + 2, fir.ss}}) != edgeset.end());
right = (edgeset.find({sec, {sec.ff + 2, sec.ss}}) != edgeset.end());
middle = (edgeset.find({{fir.ff + 2, fir.ss}, {sec.ff + 2, sec.ss}}) != edgeset.end());
if (left && right) important.ss = 3;
else if (middle) important.ss = 2;
else if (left || right) important.ss = 1;
else important.ss = 0;
} else if (fir.ss == sec.ss) {
// -2
left = (edgeset.find({{fir.ff, fir.ss - 2}, fir}) != edgeset.end());
right = (edgeset.find({{sec.ff, sec.ss - 2}, sec}) != edgeset.end());
left = (edgeset.find({{fir.ff, fir.ss - 2}, {sec.ff, sec.ss - 2}}) != edgeset.end());
if (left && right) important.ff = 3;
else if (middle) important.ff = 2;
else if (left || right) important.ff = 1;
else important.ff = 0;
// +2
left = (edgeset.find({fir, {fir.ff, fir.ss + 2}}) != edgeset.end());
right = (edgeset.find({sec, {sec.ff, sec.ss + 2}}) != edgeset.end());
left = (edgeset.find({{fir.ff, fir.ss + 2}, {sec.ff, sec.ss + 2}}) != edgeset.end());
if (left && right) important.ss = 3;
else if (middle) important.ss = 2;
else if (left || right) important.ss = 1;
else important.ss = 0;
}
imp.pb(important);
ordering[max(important.ff, important.ss)].pb(i);
}
int m = edges.size();
vector<pii> coor(m);
for (int urgency = 3; urgency >= 0; urgency--) {
for (int &cur : ordering[urgency]) {
pii fir = opts[edges[cur].ff], sec = opts[edges[cur].ss];
if (imp[cur].ff >= imp[cur].ss) {
// add
coor[cur] = {fir.ff + 1, fir.ss + 1};
} else {
// minus
coor[cur] = {sec.ff - 1, sec.ss - 1};
}
}
}
vector<int> u(m), v(m), a(m), b(m);
for (int i = 0; i < m; i++) {
u[i] = edges[i].ff;
v[i] = edges[i].ss;
a[i] = coor[i].ff;
b[i] = coor[i].ss;
}
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 <= 6) st123();
else st45();
return 1;
}
