#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
typedef long long ll;
struct Point{
int x, y, idx;
Point(){}
Point(int x, int y, int idx): x(x), y(y), idx(idx){}
bool operator<(const Point &r)const{
if(x==r.x) return x<r.x;
return y<r.y;
}
};
struct Edge{
int u, v, idx;
Edge(){}
Edge(int u, int v, int idx): u(u), v(v), idx(idx){}
bool operator==(const Edge &r)const{
return idx==r.idx;
}
};
struct dat{
int x, y;
vector<Edge> vec;
dat(){}
dat(int x, int y, vector<Edge> vec): x(x), y(y), vec(vec){}
bool operator<(const dat &r)const{
if(vec.size() != r.vec.size()) return vec.size() < r.vec.size();
return make_pair(x, y) < make_pair(r.x, r.y);
}
};
int xx[]={1, -1, 0, 0}, yy[]={0, 0, 1, -1};
int n;
Point arr[200002];
map<pair<int, int>, int> idx;
int par[200002];
int edgeU[400002], edgeV[400002], edgeCnt;
int edgeA[400002], edgeB[400002];
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[y] = x;
}
set<pair<int, int> > criticalPoints;
map<pair<int, int>, vector<pair<int, int> > > link;
int findPoint(int x, int y){
if(idx.find(make_pair(x, y)) == idx.end()) return -1;
return idx[make_pair(x, y)];
}
bool findCritical(int x, int y){
return criticalPoints.find(make_pair(x, y)) != criticalPoints.end();
}
set<pair<pair<int, int>, pair<int, int> > > avoid;
int mid(int x, int y){
return (x+y)/2;
}
map<pair<int, int>, bool> visited;
void dfs(pair<int, int> p){
int x = p.first, y = p.second;
visited[p] = 1;
for(auto nxt: link[p]){
if(visited[nxt]) continue;
if(x){
if(x == nxt.first) avoid.insert(make_pair(make_pair(x-1, mid(y, nxt.second)), make_pair(x+1, mid(y, nxt.second))));
else avoid.insert(make_pair(make_pair(mid(x, nxt.first), y-1), make_pair(mid(x, nxt.first), y+1)));
}
dfs(nxt);
}
}
bool firstTime;
int construct_roads(vector<int> x, vector<int> y) {
n = (int)x.size();
for(int i=0; i<n; i++){
arr[i] = Point(x[i], y[i], i);
par[i] = i;
idx[make_pair(x[i], y[i])] = i;
}
for(int i=0; i<n; i++){
if(findPoint(arr[i].x+2, arr[i].y) != -1){
edgeU[edgeCnt] = i, edgeV[edgeCnt] = idx[make_pair(arr[i].x+2, arr[i].y)];
edgeA[edgeCnt] = arr[i].x+1;
edgeB[edgeCnt] = (arr[i].x+arr[i].y) % 4 == 0 ? arr[i].y-1 : arr[i].y+1;
edgeCnt++;
}
if(findPoint(arr[i].x, arr[i].y+2) != -1){
edgeU[edgeCnt] = i, edgeV[edgeCnt] = idx[make_pair(arr[i].x, arr[i].y+2)];
edgeA[edgeCnt] = (arr[i].x+arr[i].y) % 4 == 0 ? arr[i].x+1 : arr[i].x-1;
edgeB[edgeCnt] = arr[i].y+1;
edgeCnt++;
}
}
for(int i=0; i<edgeCnt; i++) merge(edgeU[i], edgeV[i]);
for(int i=0; i<n; i++) if(find(0) != find(i)) return 0;
for(int i=0; i<n; i++){
if(findPoint(arr[i].x, arr[i].y+2) == -1 || findPoint(arr[i].x+2, arr[i].y) == -1 || findPoint(arr[i].x+2, arr[i].y+2) == -1) continue;
criticalPoints.insert(make_pair(arr[i].x+1, arr[i].y+1));
}
pair<int, int> origin (0, 0);
for(auto p: criticalPoints){
if((p.first+p.second)%4 == 2){
if(findCritical(p.first, p.second + 2)) link[p].push_back(make_pair(p.first, p.second+2));
if(findCritical(p.first, p.second - 2)) link[p].push_back(make_pair(p.first, p.second-2));
if(!findCritical(p.first-2, p.second)){
link[origin].push_back(make_pair(p.first-2, p.second));
link[make_pair(p.first-2, p.second)].push_back(p);
}
if(!findCritical(p.first+2, p.second)){
link[origin].push_back(make_pair(p.first+2, p.second));
link[make_pair(p.first+2, p.second)].push_back(p);
}
}
else{
if(findCritical(p.first + 2, p.second)) link[p].push_back(make_pair(p.first+2, p.second));
if(findCritical(p.first - 2, p.second)) link[p].push_back(make_pair(p.first-2, p.second));
if(!findCritical(p.first, p.second-2)){
link[origin].push_back(make_pair(p.first, p.second-2));
link[make_pair(p.first, p.second-2)].push_back(p);
}
if(!findCritical(p.first, p.second+2)){
link[origin].push_back(make_pair(p.first, p.second+2));
link[make_pair(p.first, p.second+2)].push_back(p);
}
}
}
dfs(origin);
int pnt = 0;
for(int i=0; i<edgeCnt; i++){
auto minPoint = make_pair(min(arr[edgeU[i]].x, arr[edgeV[i]].x), min(arr[edgeU[i]].y, arr[edgeV[i]].y));
auto maxPoint = make_pair(max(arr[edgeU[i]].x, arr[edgeV[i]].x), max(arr[edgeU[i]].y, arr[edgeV[i]].y));
if(avoid.find(make_pair(minPoint, maxPoint)) != avoid.end()) continue;
swap(edgeU[i], edgeU[pnt]);
swap(edgeV[i], edgeV[pnt]);
swap(edgeA[i], edgeA[pnt]);
swap(edgeB[i], edgeB[pnt]);
pnt++;
}
edgeCnt = pnt;
n = pnt+1;
build(vector<int>(edgeU, edgeU+n-1), vector<int>(edgeV, edgeV+n-1), vector<int>(edgeA, edgeA+n-1), vector<int>(edgeB, edgeB+n-1));
return 1;
}
