描述
After scrimping and saving for years, Farmer John has decided to build a new barn. He wants the barn to be highly accessible, and he knows the coordinates of the grazing spots of all N (2 ≤ N ≤ 10,000 cows. Each grazing spot is at a point with integer coordinates (Xi, Yi) (-10,000 ≤ Xi ≤ 10,000; -10,000 ≤ Yi ≤ 10,000). The hungry cows never graze in spots that are horizontally or vertically adjacent.
The barn must be placed at integer coordinates and cannot be on any cow's grazing spot. The inconvenience of the barn for any cow is given the Manhattan distance formula | X - Xi | + | Y - Yi|, where (X, Y) and (Xi, Yi) are the coordinates of the barn and the cow's grazing spot, respectively. Where should the barn be constructed in order to minimize the sum of its inconvenience for all the cows?
输入
Line 1: A single integer: N
Lines 2..N+1: Line i+1 contains two space-separated integers which are the grazing location (Xi, Yi) of cow i
输出
Line 1: Two space-separated integers: the minimum inconvenience for the barn and the number of spots on which Farmer John can build the barn to achieve this minimum.
样例输入
4
1 -3
0 1
-2 1
1 -1
样例输出
10 4
提示
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std; const int maxn=;
int n;
struct p
{
int x,y;
}a[maxn];
bool cmp1(p a,p b){return a.x<b.x;}
bool cmp2(p a,p b){return a.y<b.y;}
bool check(int xx,int yy)
{
for(int i=;i<n;i++)if(a[i].x==xx&&a[i].y==yy)return ;
return ;
}
int sum(int xx,int yy)
{
int ans=;
for(int i=;i<n;i++)
ans+=abs(xx-a[i].x)+abs(yy-a[i].y);
return ans;
}
int dx[]={,,,-};
int dy[]={,-,,};
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);
if(n%==)
{
int mid=n/;
sort(a,a+n,cmp1);
int xx=a[mid].x;
sort(a,a+n,cmp2);
int yy=a[mid].y;
if(check(xx,yy))printf("%d 1\n",sum(xx,yy));
else
{
int minn=1e9,ans=;
for(int i=;i<;i++)
{
int val=sum(xx+dx[i],yy+dy[i]);
if(val<minn)minn=val,ans=;
else if(val==minn)ans++;
}
printf("%d %d\n",minn,ans);
}
}
else
{
int mid=n/;
sort(a,a+n,cmp1);
int x1=a[mid-].x,x2=a[mid].x;
sort(a,a+n,cmp2);
int y1=a[mid-].y,y2=a[mid].y;
int ans=(x2-x1+)*(y2-y1+);
for(int i=;i<n;i++)
if(x1<=a[i].x&&a[i].x<=x2&&y1<=a[i].y&&a[i].y<=y2)
ans--;
printf("%d %d\n",sum(x1,y1),ans);
}
return ;
}