#include "parks.h"
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
struct ura
{
int a,b,tip;
};
map<pair<int,int>,int>bench;
map<pair<int,int>,int>fnt;
map<pair<int,int>,int>id;
int cbenchx[400005];
int cbenchy[400005];
vector<int> adj[200005];
int sef[200005];
int fre[200005];
int pairst[200005];
int pairdr[400005];
int dx[10]={0,0,2,-2};
int dy[10]={-2,2,0,0};
int tip[10]={0,0,10,10};
bool cmp(ura a,ura b)
{
return a.tip<b.tip;
}
int find(int a)
{
if(a==sef[a])
{
return a;
}
return sef[a]=find(sef[a]);
}
int mtc(int curr)
{
if(fre[curr]==1)
{
return 0;
}
fre[curr]=1;
for(auto x:adj[curr])
{
if(pairdr[x]==0)
{
pairst[curr]=x;
pairdr[x]=curr;
return 1;
}
}
for(auto x:adj[curr])
{
if(mtc(pairdr[x])==1)
{
pairst[curr]=x;
pairdr[x]=curr;
return 1;
}
}
return 0;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n=x.size();
vector<ura> edges;
for(int i=0;i<n;i++)
{
sef[i]=i;
//cout<<i<<" "<<x[i]<<" "<<y[i]<<'\n';
for(int z=0;z<4;z++)
{
int nx=x[i]+dx[z];
int ny=y[i]+dy[z];
if(fnt.count({nx,ny}))
{
if(x[i]==4 && nx==4)
edges.push_back({i,fnt[{nx,ny}],tip[z]+15});
else
edges.push_back({i,fnt[{nx,ny}],tip[z]});
}
}
fnt[{x[i],y[i]}]=i;
}
vector<int>u,v,a,b;
sort(edges.begin(),edges.end(),cmp);
int cntbenches=0,cntegde=0;
for(auto j:edges)
{
//cout<<j.a<<" "<<j.b<<" "<<j.tip<<'\n';
if(find(j.a)!=find(j.b))
{
sef[find(j.b)]=j.a;
u.push_back(j.a);
v.push_back(j.b);
int minx=min(x[j.a],x[j.b]);
int maxx=max(x[j.a],x[j.b]);
int miny=min(y[j.a],y[j.b]);
int maxy=max(y[j.a],y[j.b]);
cntegde++;
id[{j.a,j.b}]=cntegde;
if(minx==maxx)
{
if(bench[{minx+1,miny+1}]==0)
{
cntbenches++;
cbenchx[cntbenches]=minx+1;
cbenchy[cntbenches]=miny+1;
bench[{minx+1,miny+1}]=cntbenches;
}
if(bench[{minx-1,miny+1}]==0)
{
cntbenches++;
cbenchx[cntbenches]=minx-1;
cbenchy[cntbenches]=miny+1;
bench[{minx-1,miny+1}]=cntbenches;
}
adj[cntegde].push_back({bench[{minx+1,miny+1}]});
adj[cntegde].push_back({bench[{minx-1,miny+1}]});
}
else
{
if(bench[{minx+1,miny+1}]==0)
{
cntbenches++;
cbenchx[cntbenches]=minx+1;
cbenchy[cntbenches]=miny+1;
bench[{minx+1,miny+1}]=cntbenches;
}
if(bench[{minx+1,miny-1}]==0)
{
cntbenches++;
cbenchx[cntbenches]=minx+1;
cbenchy[cntbenches]=miny-1;
bench[{minx+1,miny-1}]=cntbenches;
}
adj[cntegde].push_back({bench[{minx+1,miny+1}]});
adj[cntegde].push_back({bench[{minx+1,miny-1}]});
}
}
}
//cout<<cntegde<<'\n';
int matched=1,cntmatch=0;
while(matched==1)
{
matched=0;
for(int i=1;i<=cntegde;i++)
{
fre[i]=0;
}
for(int i=1;i<=cntegde;i++)
{
if(pairst[i]==0)
{
int rez=mtc(i);
matched|=rez;
cntmatch+=rez;
}
}
}
if(cntmatch==n-1)
{
for(int i=1;i<=n-1;i++)
{
a.push_back(cbenchx[pairst[i]]);
b.push_back(cbenchy[pairst[i]]);
}
build(u,v,a,b);
return 1;
}
return 0;
}
