/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void build (vector <int> U, vector <int> V, vector <int> A, vector <int> B);
struct Point {
int x, y;
int id;
};
bool operator < (const Point &u, const Point &v) {
return make_pair(u.x, u.y) < make_pair(v.x, v.y);
}
bool operator != (const Point &u, const Point &v) {
return make_pair(u.x, u.y) != make_pair(v.x, v.y);
}
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int N;
set <Point> fountains;
set <pair <Point, Point>> roads;
set <Point> benches;
set <Point> squares;
map <Point, vector <Point>> adj;
set <Point> seen;
void DFS (Point s) {
seen.insert(s);
for (Point t : adj[s]) {
if (seen.find(t) == seen.end()) {
if (s.x == t.x) {
roads.erase(make_pair(Point{s.x - 1, (s.y + t.y) / 2}, Point{s.x + 1, (s.y + t.y) / 2}));
} else {
roads.erase(make_pair(Point{(s.x + t.x) / 2, s.y - 1}, Point{(s.x + t.x) / 2, s.y + 1}));
}
DFS(t);
}
}
}
set <pair <Point, Point>> used;
map <Point, Point> root;
Point findRoot (Point u) {
if (root.find(u) == root.end()) {
return u;
} else {
return root[u] = findRoot(root[u]);
}
}
bool join (Point u, Point v) {
u = findRoot(u);
v = findRoot(v);
if (u != v) {
root[u] = v;
return true;
} else {
return false;
}
}
int construct_roads (vector <int> X, vector <int> Y) {
N = (int) X.size();
for (int i = 0; i < N; i++) {
fountains.insert(Point{X[i], Y[i], i});
}
// Find all usable benches
for (Point f : fountains) {
for (int d = 0; d < 2; d++) {
Point g = Point{f.x + dx[d] * 2, f.y + dy[d] * 2};
if (fountains.find(g) != fountains.end()) {
roads.insert(make_pair(f, g));
if (f.x == g.x) {
benches.insert(Point{f.x - 1, (f.y + g.y) / 2});
benches.insert(Point{f.x + 1, (f.y + g.y) / 2});
} else {
benches.insert(Point{(f.x + g.x) / 2, g.y - 1});
benches.insert(Point{(f.x + g.x) / 2, g.y + 1});
}
}
}
}
// Find all squares
for (Point f : fountains) {
bool isSquare = true;
for (int dx : {0, +2}) {
for (int dy : {0, +2}) {
isSquare &= (fountains.find(Point{f.x + dx, f.y + dy}) != fountains.end());
}
}
if (isSquare == true) {
squares.insert(Point{f.x + 1, f.y + 1});
}
}
// Build the dual graph
for (Point s : squares) {
for (int d = abs(s.x + s.y) / 2 % 2; d < 4; d += 2) {
Point t = Point{s.x + dx[d] * 2, s.y + dy[d] * 2};
if (squares.find(t) == squares.end()) {
adj[Point{-7, -7}].push_back(t);
}
adj[t].push_back(s);
}
}
// Run DFS and cut edges
DFS(Point{-7, -7});
for (pair <Point, Point> r : roads) {
if (join(r.first, r.second) == true) {
used.insert(r);
}
}
if ((int) used.size() < N - 1) {
return 0;
}
// Build answer
vector <int> U, V, A, B;
for (Point b : benches) {
if (abs(b.x + b.y) / 2 % 2 == 1) {
for (int dx : {-1, +1}) {
Point f = Point{b.x + dx, b.y - 1};
Point g = Point{b.x + dx, b.y + 1};
if (used.find(make_pair(f, g)) != used.end()) {
U.push_back(fountains.find(f)->id);
V.push_back(fountains.find(g)->id);
A.push_back(b.x);
B.push_back(b.y);
}
}
} else {
for (int dy : {-1, +1}) {
Point f = Point{b.x - 1, b.y + dy};
Point g = Point{b.x + 1, b.y + dy};
if (used.find(make_pair(f, g)) != used.end()) {
U.push_back(fountains.find(f)->id);
V.push_back(fountains.find(g)->id);
A.push_back(b.x);
B.push_back(b.y);
}
}
}
}
build(U, V, A, B);
return 1;
}
