#include "parks.h"
using namespace std;
#include<bits/stdc++.h>
#define vec vector
#define coord pair<int, int>
#define fst first
#define snd second
void dfs(int u, set<int>& vis, vec<vec<int>>& g, vec<int>& us, vec<int>& vs) {
reverse(g[u].begin(), g[u].end());
for(int v : g[u]) {
if(vis.find(v) != vis.end()) {
continue;
}
vis.insert(v);
us.push_back(u);
vs.push_back(v);
dfs(v, vis, g, us, vs);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
// construct graph
map<coord, int> points;
for(int i = 0; i<n; i++) points.insert({{x[i], y[i]}, i});
vec<vec<int>> g(n);
for(int i = 0; i<n; i++) {
vec<coord> pot_neigh = {{x[i]+2, y[i]}, {x[i], y[i]+2}};
for(coord c : pot_neigh) {
auto it = points.find(c);
if(it == points.end()) continue;
int j = (*it).snd;
g[i].push_back(j);
g[j].push_back(i);
}
}
// use dfs tree of the graph to construct u and v
vec<int> us(0), vs(0);
set<int> vis;
vis.insert(0);
dfs(0, vis, g, us, vs);
if(us.size() != n-1) {
return 0;
}
// for each edge of the tree, create set of two red points it can use, and for each red point, corresponding edges that want it
vec<set<coord>> edge_red_points(n-1);
map<coord, set<int>> red_point_edges;
for(int i = 0; i<n-1; i++) {
vec<coord> eps{{x[us[i]], y[us[i]]}, {x[vs[i]], y[vs[i]]}};
sort(eps.begin(), eps.end());
set<coord> red_points;
if(eps[0].fst == eps[1].fst) {
red_points.insert({eps[0].fst+1, (eps[0].snd+eps[1].snd)/2});
red_points.insert({eps[0].fst-1, (eps[0].snd+eps[1].snd)/2});
}
else {
red_points.insert({(eps[0].fst+eps[1].fst)/2, eps[0].snd+1});
red_points.insert({(eps[0].fst+eps[1].fst)/2, eps[0].snd-1});
}
edge_red_points[i] = red_points;
for(coord _coord : red_points) {
red_point_edges[_coord].insert(i);
}
}
// assign red points to edges, iterate from first edge to last, if it isn't assigned, give it any of the two, as long as there are edges that have only one avilable as consequence assign them that one availble
vec<bool> ass(n-1, false);
vec<int> ass_xs(n-1);
vec<int> ass_ys(n-1);
for(auto red_point : red_point_edges) {
if(red_point.snd.size() == 1) {
int edge = *(red_point.snd.begin());
ass[edge] = true;
ass_xs[edge] = red_point.fst.fst;
ass_ys[edge] = red_point.fst.snd;
}
}
for(int i = 0; i<n-1; i++) {
if(ass[i]) continue;
assert(edge_red_points[i].size() == 2);
coord red_point = *edge_red_points[i].begin();
red_point_edges[red_point].erase(i);
edge_red_points[i].erase(red_point);
ass[i] = true;
ass_xs[i] = red_point.fst;
ass_ys[i] = red_point.snd;
vec<coord> rem_red_points{red_point};
while(rem_red_points.size() > 0) {
red_point = rem_red_points.back();
rem_red_points.pop_back();
for(int j : red_point_edges[red_point]) {
if(ass[j]) {
continue;
}
edge_red_points[j].erase(red_point);
assert(edge_red_points[j].size() == 1);
coord other = *edge_red_points[j].begin();
ass[j] = true;
ass_xs[j] = other.fst;
ass_ys[j] = other.snd;
red_point_edges[other].erase(j);
edge_red_points[j].erase(red_point);
rem_red_points.push_back(other);
}
}
}
build(us, vs, ass_xs, ass_ys);
return 1;
}
