#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>
#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define N 100005
#define M 200005
#define seed 23333
using namespace std;
const int inf=(int)1e9;
int i,j,m,n,p,k,A[N],B[N],l;
map<pair<int,int>,int>mp;
vector<int>v[M];
int f[2][N],ans,sum[N],size[2],now,last;
int RE()
{
puts("-1");
exit(0);
}
int main()
{
scanf("%d",&n); ans=2*n-2;
for (i=1;i<=n;++i)
{
scanf("%d%d",&A[i],&B[i]);
mp[mk(A[i],B[i])]=1;
if (i!=1&&!A[i]) RE();
if (i!=2&&!B[i]) RE();
}
for (i=1;i<=n;++i)
{
if (i!=1&&mp.find(mk(A[i]-1,B[i]))==mp.end()&&
mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
mp.find(mk(A[i]-1,B[i]+1))==mp.end()) RE();
if (i!=2&&mp.find(mk(A[i],B[i]-1))==mp.end()&&
mp.find(mk(A[i]-1,B[i]-1))==mp.end()&&
mp.find(mk(A[i]+1,B[i]-1))==mp.end()) RE();
v[A[i]+B[i]].pb(A[i]);
}
for (i=1;i<=2*n;++i)
if (v[i].size())
{
A[0]=B[0]=0;
for (j=0;j<(int)v[i].size();++j) A[++A[0]]=v[i][j],B[++B[0]]=v[i][j];
sort(B+1,B+B[0]+1); B[0]=unique(B+1,B+B[0]+1)-(B+1);
for (j=1;j<=B[0];++j) sum[j]=0;
for (j=1;j<=A[0];++j) sum[lower_bound(B+1,B+B[0]+1,A[j])-B]++;
size[0]=size[1]=now=last=0; now=1;
size[1]=sum[1];
if (mp.find(mk(B[1]-1,i-B[1]-1))!=mp.end())
for (j=0;j<=size[now];++j) f[now][j]=size[now]-j;
for (j=2;j<=B[0];++j)
{
now^=1; last=now^1;
for (l=0;l<=size[now];++l) f[now][l]=0;
if (mp.find(mk(B[1]-1,i-B[1]-1))==mp.end())
{
for (l=0;l<=size[last];++l)
f[now][sum[j]]=max(f[now][sum[j]],f[last][l]+min(sum[j],l));
}
else
{
int Max=-inf;
for (l=0;l<=size[now];++l)
{
if (l<=size[last]) Max=max(Max,f[last][l]+l);
f[now][l]=Max;
}
Max=-inf;
for (l=max(size[last],size[now]);l>=0;--l)
{
if (l<=size[last]) Max=max(Max,f[last][l]);
if (l<=size[now])
f[now][l]=max(f[now][l],Max+l);
}
for (l=0;l<=size[now];++l)
f[now][l]+=(size[now]-l);
}
size[now]=sum[j];
}
int Max=0;
for (j=0;j<=size[now];++j) Max=max(Max,f[now][j]);
ans-=Max;
}
printf("%d\n",ans);
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:37:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n); ans=2*n-2;
^
./Main.cpp:40:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&A[i],&B[i]);
^