/*EOJ 2614*/  #include<iostream>
using namespace std;
#define maxn 102
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
int x[maxn],y[maxn];
int dist[maxn][maxn],best[maxn],pre[maxn];
bool visit[maxn];
int maxbetween[maxn][maxn];
int n;
void calc()
   {
 for(int i=0;i<n;i++)
  {
dist[i][i]=0;
for(int j=0;j<i;j++)
dist[i][j]=dist[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
 }
 }
int prim()
{
int i,j,k;
int ans=0,smin;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
maxbetween[i][j]=0;
for(i=0;i<n;i++)
{
visit[i]=0;
best[i]=dist[0][i];
pre[i]=0;
//maxbetween[0][i]=maxbetween[i][0]=dist[0][i];
}
visit[0]=1;
for(i=1;i<n;i++)
{
smin=INT_MAX;
for(j=0;j<n;j++)
{
if(!visit[j] && best[j]<smin)
{
smin=best[j];
k=j;
}
}
for(j=0;j<n;j++)
{
if(visit[j])
{
maxbetween[j][k]=maxbetween[k][j]=max(maxbetween[j][pre[k]],smin);//
}
}
visit[k]=1;
ans+=smin;
for(j=0;j<n;j++)
{
if(!visit[j] && dist[k][j]<best[j])
{
best[j]=dist[k][j];
pre[j]=k;
}
}
}
return ans;
}
int secondprim(int total)
{
int ans=INT_MAX;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i!=j && i!=pre[j] && j!=pre[i])
ans=min(ans,total-maxbetween[i][j]+dist[i][j]);
}
return ans;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
calc();
int total=prim();
int t=secondprim(total);
printf("%d\n",total);
if(t==total)
printf("Yes\n");
else printf("No\n");
}
return 0;
}
|