#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//#define //bug(x) // cout << #x << " " << x << endl;
struct Point{
int x, y, id; Point( int x = 0, int y = 0, int id = 0 ) : x(x), y(y), id(id) {}
bool operator < ( Point p ) const{
if( y == p.y ) return x < p.x;
return y < p.y;
}
};
struct Edge{
int x1, y1, x2, y2; Edge( int a1, int b1, int a2, int b2 ) : x1( min( a1, a2 ) ), x2( max( a1, a2 ) ), y1( min( b1, b2 ) ), y2( max( b1, b2 )){}
bool operator < ( Edge e ) const{
if( x1 != e.x1 ) return x1 < e.x1;
if( x2 != e.x2 ) return x2 < e.x2;
if( y1 != e.y1 ) return y1 < e.y1;
return y2 < e.y2;
}
};
int construct_roads( vector<int> x, vector<int> y ){
int n = x.size();
vector<int> pai(n), grau(n);
iota( pai.begin(), pai.end(), 0 );
auto find = [&]( Point p, set<Point>& s ){
return s.find(p) != s.end();
};
auto find2 = [&]( Edge p, set<Edge>& s ){
return s.find(p) != s.end();
};
function<int(int)> get_rep = [&]( int a ){
return (( pai[a] == a ) ? a : pai[a] = get_rep(pai[a]));
};
set<Point> s;
for( int i = 0; i < n; i++ ) s.insert(Point(x[i], y[i], i));
set<Edge> edges, evitar;
int cont = 0;
for( auto cur : s ){
if( find( Point( cur.x + 2, cur.y, 0 ), s ) ){
auto it = s.find(Point( cur.x + 2, cur.y, 0 ) );
grau[it->id]++;
grau[cur.id]++;
pai[get_rep(it->id)] = get_rep(cur.id);
cont++;
edges.insert(Edge(cur.x, cur.y, cur.x + 2, cur.y) );
}
}
for( auto cur : s ){
if( find( Point( cur.x, cur.y - 2, 0 ), s ) && !find2( Edge( cur.x, cur.y, cur.x, cur.y - 2), evitar ) ){
auto it = s.find(Point(cur.x, cur.y - 2, 0 ));
if( get_rep(it->id) != get_rep(cur.id) ){
pai[get_rep(it->id)] = get_rep(cur.id);
grau[cur.id]++;
grau[it->id]++;
edges.insert(Edge( cur.x, cur.y, cur.x, cur.y - 2 ) );
cont++;
}
}
}
map<Point, int> mp;
for( auto cur : edges ){
// cout << cur.x1 << " " << cur.y1 << " " << cur.x2 << " " << cur.y2 << endl;
if( cur.x1 == cur.x2 ){
mp[Point(cur.x1 - 1, (cur.y1 + cur.y2)/2, 0 )]++;
mp[Point(cur.x1 + 1, (cur.y1 + cur.y2)/2, 0 )]++;
}
else{
mp[Point( (cur.x1 + cur.x2)/2, cur.y1 - 1, 0 )]++;
mp[Point( (cur.x1 + cur.x2)/2, cur.y1 + 1, 0 )]++;
}
}
set<pair<int, Point>> ordem;
set<Point> bancos;
for( auto [p, val] : mp ) ordem.insert({ val, p }), bancos.insert(p);
int dx[] = { 1, 1, -1, -1 };
int dy[] = { 1, -1, -1, 1 };
vector<int> resp[4];
while( !ordem.empty() ){
auto [val, p] = *ordem.begin(); ordem.erase(ordem.begin());
bancos.erase(p);
bool ok = false;
// cout << "---- " << p.x << " " << p.y << endl;
for( int d1 = 0, d2 = 1; d1 < 4 && !ok ; d1++, d2 = ( d2 + 1 )%4 ){
int x1 = p.x + dx[d1], y1 = p.y + dy[d1];
int x2 = p.x + dx[d2], y2 = p.y + dy[d2];
int x3 = p.x + dx[d1] + dx[d2], y3 = p.y + dy[d1] + dy[d2];
// //bug(dx[d1]);
// //bug(dx[d2]);
// //bug(dy[d1]);
// //bug(dy[d2]);
// cout << x3 << " " << y3 << endl;
//bug(x1);
//bug(y1);
//bug(x2);
//bug(y2);
Edge e = Edge( x1, y1, x2, y2 );
//bug(find( Point( x3, y3, 0 ), bancos ));
//bug(find2( e, edges ));
if( find2( e, edges ) && !find( Point( x3, y3, 0 ), bancos ) ){
Point p1 = *s.find( Point( x1, y1, 0 ) ), p2 = *s.find( Point( x2, y2, 0 ) );
resp[0].push_back(p1.id);
resp[1].push_back(p2.id);
resp[2].push_back(p.x);
resp[3].push_back(p.y);
ok = true;
// cout << p1.id << " " << p2.id << " " << p.x << " " << p.y << endl;
edges.erase(e);
if( e.x1 == e.x2 ){
ordem.erase({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});
mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )]++;
ordem.insert({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});
ordem.erase({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )]++;
ordem.insert({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
}
else{
ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});
mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )]++;
ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});
ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});
mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )]++;
ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});
}
}
}
for( int d1 = 0, d2 = 1; d1 < 4 && !ok ; d1++, d2 = ( d2 + 1 )%4 ){
int x1 = p.x + dx[d1], y1 = p.y + dy[d1];
int x2 = p.x + dx[d2], y2 = p.y + dy[d2];
int x3 = p.x + dx[d1] + dx[d2], y3 = p.y + dy[d1] + dy[d2];
Edge e = Edge( x1, y1, x2, y2 );
// cout << x3 << " " << y3 << endl;
if( find2( e, edges ) ){
Point p1 = *s.find( Point( x1, y1, 0 ) ), p2 = *s.find( Point( x2, y2, 0 ) );
resp[0].push_back(p1.id);
resp[1].push_back(p2.id);
resp[2].push_back(p.x);
resp[3].push_back(p.y);
ok = true;
// cout << p1.id << " " << p2.id << " " << p.x << " " << p.y << endl;
edges.erase(e);
if( e.x1 == e.x2 ){
ordem.erase({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});
mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )]++;
ordem.insert({ mp[Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 - 1, (e.y1 + e.y2)/2, 0 )});
ordem.erase({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )]++;
ordem.insert({ mp[Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )], Point(e.x1 + 1, (e.y1 + e.y2)/2, 0 )});
}
else{
ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});
mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )]++;
ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 - 1, 0 )});
ordem.erase({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});
mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )]++;
ordem.insert({ mp[Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )], Point( (e.x1 + e.x2)/2, e.y1 + 1, 0 )});
}
}
}
ordem.erase({ mp[p], p });
}
build( resp[0], resp[1], resp[2], resp[3] );
return cont == n - 1;
// set<Edge> evitar;
//
// for( auto cur : s ){
// if( find( Point( cur.x, cur.y - 1, 0 ), s ) && !find( Edge( cur.x, cur.y, cur.x, cur.y - 1 ), evitar ) ){
//
// }
// }
}
