#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> par;
vector<int> sz;
dsu(int n) : par(n,-1) {sz.assign(n,1);}
int get(int x) {
if(par[x]==-1) return x;
return par[x]=get(par[x]);
}
void merge(int x, int y) {
int px=get(x), py=get(y);
if(px==py) return ;
if(sz[px]>sz[py]) {
swap(px,py);
swap(x,y); //:) lyft
}
sz[py]+=sz[px];
par[px]=py;
}
};
int d0[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
pair<int,int> kp(pair<int,int> a, pair<int,int> b) {
return {(a.first+b.first)/2, (a.second+b.second)/2};
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n=x.size();
vector<pair<pair<int,int>, int>> ord;
vector<pair<int,int>> lst;
for(int i=0;i<n;++i) {
ord.push_back({{x[i], y[i]}, i});
lst.push_back({x[i], y[i]});
}
sort(ord.begin(), ord.end());
auto ker=[&](pair<int,int> coords) -> int {
auto it=lower_bound(ord.begin(), ord.end(), make_pair(coords, 0));
if(it==ord.end() || it->first!=coords) return -1;
return it->second;
};
dsu d(n);
vector<pair<int,int>> edgs;
for(int i=0;i<n;++i) {
for(int j=0;j<4;++j) {
int nx=x[i]+d0[j][0]*2, ny=y[i]+d0[j][1]*2;
int ind=ker(make_pair(nx,ny));
if(ind!=-1) {
if(d.get(i)!=d.get(ind)) {
d.merge(i, ind);
edgs.push_back({i, ind});
}
}
}
}
if(d.sz[d.get(0)]!=n) {
return 0;
}
map<pair<int,int>, int> cnt;
set<pair<int, pair<int,int>>> st;
map<pair<int,int>, int> in_st;
for(int i=0;i<(int)edgs.size();++i) {
st.insert({0, edgs[i]});
in_st[edgs[i]]=1;
}
map<pair<int,int>, pair<int,int>> kozpont;
for(int i=0;i<(int)edgs.size();++i) {
kozpont[kp(lst[edgs[i].first], lst[edgs[i].second])]=edgs[i];
}
map<pair<int,int>, pair<int,int>> rel;
set<pair<int,int>> benches_set;
while(!st.empty()) {
auto akt=*st.begin();st.erase(st.begin());
in_st[akt.second]=0;
if(akt.first==-2) assert(0);
pair<int,int> first_point=lst[akt.second.first];
pair<int,int> second_point=lst[akt.second.second];
pair<int,int> alt1=kp(first_point, second_point);
pair<int,int> alt2=alt1;
if(first_point.first!=second_point.first) {
alt1.second--;
alt2.second++;
}else {
alt1.first--;
alt2.first++;
}
pair<int,int> bench;
if(benches_set.find(alt1)==benches_set.end()) {
bench=alt1;
}else if(benches_set.find(alt2)==benches_set.end()) {
bench=alt2;
}else {
assert(0); //?
}
rel[akt.second]=bench;
for(int i=0;i<4;++i) {
int nx=bench.first+d0[i][0], ny=bench.second+d0[i][1];
pair<int,int> ind={nx,ny};
if(kozpont.count(ind) && in_st[kozpont[ind]]) {
st.erase({cnt[kozpont[ind]]--, kozpont[ind]});
st.insert({cnt[kozpont[ind]], kozpont[ind]});
}
}
}
vector<pair<int,int>> benches(edgs.size());
for(int i=0;i<(int)edgs.size();++i) {
benches[i]=rel[edgs[i]];
}
vector<int> A(edgs.size()),B(edgs.size()),C(edgs.size()),D(edgs.size());
for(int i=0;i<(int)edgs.size();++i) A[i]=edgs[i].first;
for(int i=0;i<(int)edgs.size();++i) B[i]=edgs[i].second;
for(int i=0;i<(int)edgs.size();++i) C[i]=benches[i].first;
for(int i=0;i<(int)edgs.size();++i) D[i]=benches[i].second;
build(A,B,C,D);
return 1;
}
