#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int U = 1.01e5;
struct Segment{
int x, y;
bool vert;
};
struct Range{
int a, b;
};
struct Dsu{
Dsu(int n_) : p(n_, -1){}
int f(int x){
return p[x] < 0 ? x : p[x] = f(p[x]);
}
bool u(int a, int b){
a = f(a);
b = f(b);
if(a == b) return false;
p[b] = a;
return true;
}
vector<int> p;
};
// 2-sat in linear time via backtracking.
class Two_Sat {
public:
int N; // number of variables
vector<int> val; // assignment of x is at val[2x] and -x at val[2x+1]
vector<char> valid; // changes made at time i are kept iff valid[i]
vector<vector<int> > G; // graph of implications G[x][i] = y means (x -> y)
Two_Sat(int N_) : N(N_) { // create a formula over N variables (numbered 1 to N)
G.resize(2*N);
}
int add_variable() {
G.emplace_back();
G.emplace_back();
return N++;
}
private:
// converts a signed variable index to its position in val[] and G[]
int to_ind(int x) {
return 2*(abs(x)-1) + (x<0);
}
// Add a directed edge to the graph.
// You most likely do not want to call this yourself!
void add_edge(int a, int b) {
G[to_ind(a)].push_back(to_ind(b));
}
int time() {
return valid.size()-1;
}
bool dfs(int x) {
if(valid[abs(val[x])]) return val[x]>0;
val[x] = time();
val[x^1] = -time();
for(int e:G[x])
if(!dfs(e))
return false;
return true;
}
public:
// Add the or-clause: (a or b)
void add_or(int a, int b) {
add_edge(-a,b);
add_edge(-b,a);
}
// Add the implication: a -> b
void add_implication(int a, int b) {
add_or(-a, b);
}
// Add condition: x is true
void add_true(int x) {
add_or(x,x);
}
// At most one with linear number of clauses
template<typename T>
void add_at_most_one(T vars) {
if(vars.begin() == vars.end()) return;
int last = *vars.begin();
int cur = 0;
for(int const&e:vars){
if(e == last) continue;
if(cur == 0) cur = e;
else {
add_or(-cur, -e);
int new_cur = add_variable();
cur = add_implication(cur, new_cur);
add_implication(e, new_cur);
cur = new_cur;
}
}
if(cur != 0){
add_or(-cur, -last);
}
}
bool solve() {
val.assign(2*N, 0);
valid.assign(1, 0);
for(int i=0; i<(int)val.size(); i+=2) {
if(!valid[abs(val[i])]) {
valid.push_back(1);
if(!dfs(i)) {
valid.back()=0;
valid.push_back(1);
if(!dfs(i+1)) return false;
}
}
}
return true;
}
};
int construct_roads(vector<int> X, vector<int> Y) {
const int n = X.size();
map<pair<int, int>, int> decode;
for(int i=0; i<n; ++i){
decode[make_pair(X[i], Y[i])] = i;
}
vector<array<int, 4> > to(n, {-1, -1, -1, -1});
vector<array<int, 4> > var(n, {0, 0, 0, 0});
int vars = 0;
for(int i=0; i<n; ++i){
for(int j=0; j<4; ++j){
int x = X[i], y = Y[i];
if(j == 0) x+=2;
if(j == 2) x-=2;
if(j == 1) y+=2;
if(j == 3) y-=2;
if(decode.count(make_pair(x, y))){
to[i][j] = decode[make_pair(x, y)];
if(var[i][j] == 0){
++vars;
var[i][j] = vars;
var[to[i][j]][j^2] = vars;
}
//cerr << i << " " << X[i] << " " << Y[i] << " with " << j << " -> " << x << " " << y << " " << to[i][j] << " " << var[i][j] << "\n";
}
}
}
Two_Sat sat(vars);
auto check = [&](int a, int b){
if(a == 0 || b == 0) return;
//cerr << "or " << a << " " << b << "\n";
sat.add_or(a, b);
};
for(int i=0; i<n; ++i){
check(var[i][0], var[i][1]);
check(var[i][2], -var[i][1]);
check(-var[i][2], -var[i][3]);
check(-var[i][0], var[i][3]);
}
assert(sat.solve());
Dsu uni(n);
vector<int> out_a, out_b, out_x, out_y;
for(int i=0; i<n; ++i){
for(int j=0; j<4; ++j) if(to[i][j] != -1){
const int e = to[i][j];
if(uni.u(i, e)){
out_a.push_back(i);
out_b.push_back(e);
int x = X[i];
int y = Y[i];
if(j == 0) x+=1;
if(j == 2) x-=1;
if(j == 1) y+=1;
if(j == 3) y-=1;
int add;
if(sat.val[2*var[i][j]-2]>0){
add = 1;
} else {
add = -1;
}
if(j%2 == 0) y += add;
else x += add;
out_x.push_back(x);
out_y.push_back(y);
}
}
}
if((int)out_x.size() == n-1){
build(out_a, out_b, out_x, out_y);
return 1;
}
return 0;
}
