#include "parks.h"
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxN = 200'000;
const int MX = 1'000'000;
vector<int> fountain_edge[maxN];
vector<int> fountain_visit(maxN, 0);
int visit_count = 0;
void fountain_dfs(int u)
{
fountain_visit[u] = 1;
visit_count++;
for(int v: fountain_edge[u])
{
if(fountain_visit[v]) continue;
fountain_dfs(v);
}
}
struct point
{
int i;
int x;
int y;
};
bool operator < (point A, point B)
{
if(A.x == B.x) return A.y < B.y;
return A.x < B.x;
};
int N;
vector<int> X, Y;
set<point> fountains;
int point_index(int x, int y)
{
set<point>::iterator it = fountains.find(point{-1, x, y});
if(it == fountains.end()) return -1;
else return it->i;
}
struct path
{
int i;
int a;
int b;
path(int A, int B)
{
a = min(A, B);
b = max(A, B);
}
path(int I, int A, int B)
{
i = I;
a = min(A, B);
b = max(A, B);
}
};
bool operator < (path P, path Q)
{
if(P.a == Q.a) return P.b < Q.b;
return P.a < Q.a;
}
vector<path> temp_paths;
set<path> paths;
struct bench
{
int i;
int x;
int y;
};
bool operator < (bench C, bench D)
{
if(C.x == D.x) return C.y < D.y;
return C.x < D.x;
}
set<bench> benches;
int bench_index(int x, int y)
{
set<bench>::iterator it = benches.find(bench{-1, x, y});
if(it == benches.end()) return -1;
else return it->i;
}
vector<path>* bench_edge = new vector<path>[MX];
vector<int> bench_visit(MX, 0);
vector<int> U, V, A, B;
vector<int> parent(maxN);
vector<int> siz(maxN, 1);
int getRoot(int u)
{
int v;
for(v = u; parent[v] != v; v = parent[v]);
parent[u] = v;
return v;
}
void join(int u, int v)
{
u = getRoot(u);
v = getRoot(v);
if(siz[u] < siz[v]) swap(u, v);
parent[v] = u;
}
bool connected(int u, int v)
{
return getRoot(u) == getRoot(v);
}
int construct_roads(vector<int> x, vector<int> y)
{
// cerr << "check\n";
X = x;
Y = y;
N = X.size();
for(int i = 0; i < N; i++)
fountains.insert(point{i, x[i], y[i]});
// cerr << "check 2\n";
for(int i = 0; i < N; i++)
{
int I;
I = point_index(x[i] - 2, y[i]);
if(I != -1)
{
// cerr << i << ' ' << I << '\n';
fountain_edge[i].push_back(I);
fountain_edge[I].push_back(i);
temp_paths.push_back(path(i, I));
// cerr << temp_paths.size() << '\n';
}
I = point_index(x[i], y[i] - 2);
if(I != -1)
{
// cerr << i << ' ' << I << '\n';
fountain_edge[i].push_back(I);
fountain_edge[I].push_back(i);
temp_paths.push_back(path(i, I));
// cerr << temp_paths.size() << '\n';
}
}
// cerr << temp_paths.size() << '\n';
// cerr << "check 3\n";
fountain_dfs(0);
if(visit_count != N)
{
return 0;
}
int path_id = -1;
for(path p: temp_paths)
{
path_id++;
// cerr << "P -> " << path_id << ' ' << p.a << ' ' << p.b << '\n';
paths.insert(path(path_id, p.a, p.b));
}
// cerr << "check 4\n";
int bench_id = -1;
for(path p: paths)
{
// cerr << "p = " << p.i << ' ' << p.a << ' ' << p.b << '\n';
int x1 = X[p.a];
int y1 = Y[p.a];
int x2 = X[p.b];
int y2 = Y[p.b];
bench new_bench;
if(x1 == x2)
{
if( ((x1+1) + (y1+y2)/2) % 4 == 0 )
new_bench = bench{-1, x1+1, (y1+y2)/2};
else
new_bench = bench{-1, x1-1, (y1+y2)/2};
}
else
{
if( ((x1+x2)/2 + (y1+1)) % 4 == 2 )
new_bench = bench{-1, (x1+x2)/2, y1+1};
else
new_bench = bench{-1, (x1+x2)/2, y1-1};
}
int curr_bench_index;
// cerr << "before I\n";
int I = bench_index(new_bench.x, new_bench.y);
if(I == -1)
{
bench_id++;
curr_bench_index = bench_id;
new_bench.i = curr_bench_index;
benches.insert(new_bench);
}
else
{
curr_bench_index = I;
}
bench_edge[curr_bench_index].push_back(p);
}
// cerr << "check 5\n";
for(int i = 0; i < N; i++)
parent[i] = i;
for(int i = 0; i <= bench_id; i++)
{
sort(bench_edge[i].begin(), bench_edge[i].end(), [] (path P1, path P2)
{
if(X[P1.a] == X[P1.b]) return Y[P1.a] < Y[P1.b];
else return X[P1.a] < X[P1.b];
});
}
// cerr << "check 6\n";
for(bench q: benches)
{
for(path z: bench_edge[q.i])
{
if(connected(z.a, z.b)) continue;
U.push_back(z.a);
V.push_back(z.b);
A.push_back(q.x);
B.push_back(q.y);
join(z.a, z.b);
break;
}
}
// cerr << "check 7\n";
build(U, V, A, B);
return 1;
}
