题意
B 君的第三题(zhengzhou)
题目描述
让你在战争和耻辱中做一块选择，你选择耻辱，可你将来还得进行战争。
在平面上有n 个整点（横纵坐标都是整数）
B 君想找到一个整点，使得这个点，到所有点的距离之和最小。
两个点的距离定义为从一个点到到另一个点的最小步数。
其中每步可以走向相邻8 个点（上，下，左，右，左上，左下，右上，右下，类似国际象棋中的王）走一步。
输出这个最小的距离之和。
和这个点选择的方案数。（即有多少个点，可以达到这个最小的距离）
输入格式
第一行一个整数n 表示点数。
接下来n 行，每行两个整数x， y。描述一个点。
输出格式
第一行输出最小的距离之和。
第二行输出有多少个点，可以达到这个最小距离。
样例输入一
4
0 0
0 2
2 0
2 2
样例输出一
4
1
样例解释一
选择(1, 1)。
样例输入二
4
2 1
1 2
0 1
1 0
样例输出二
4
5
样例解释二
可以选择输入的4 个点之一，或者(1, 1)。
样例输入三
3
0 1
1 0
0 0
样例输出三
2
3
样例解释三
可以选择输入的3 个点之一。
数据规模与约定
对于100% 的数据，满足(1 leq n leq 10^5，|x|, |y| leq 10^9)。
对于40% 的数据，满足(1 leq n leq 10^2，|x|, |y| leq 10^2)。
对于以上每部分数据，都有50% 的数据n 是奇数。
注意数据范围是x 和y 的绝对值，x 和y 可以是负数。
分析
题目中描述的距离就是切比雪夫距离，转化为曼哈顿距离后发现，要求的就是找一个点((x,y))使得
[sum_{i=1}^n(|x-x_i|+|y-y_i|) \
= sum_{i=1}^n|x-x_i| + sum_{i=1}^n|y-y_i|
]
最小。
显然应该选取xi和yi的中位数。
程序实现的时候把曼哈顿距离下的点横纵坐标都乘2，方便判断小数部分是不是0.5。
但是有问题，就是选出来的在曼哈顿距离下是整点，但在切比雪夫距离下不一定是整点。
所以需要分类讨论。
- 能选的只有一个点，但这个点不是整点，所以要想四周抖动。
- 能选的是一个范围，所以要奇偶配对。
代码
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#include<cassert>
#define rg register
#define il inline
#define co const
#pragma GCC optimize ("O0")
using namespace std;
template<class T> il T read()
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return data*w;
}
template<class T> il T read(T&x)
{
return x=read<T>();
}
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=1e5+7;
int n;
ll x[MAXN],y[MAXN];
ll ans,cnt;
void calc(ll x,ll y)
{
ll t=0;
for(int i=0;i<n;++i)
{
t+=abs(::x[i]-x)+abs(::y[i]-y);
}
if(ans>t)
{
ans=t;
cnt=1;
}
else if(ans==t)
{
++cnt;
}
}
ll odd(ll L,ll R)
{
ll t=R-L+1;
if((L&1)&&(R&1))
{
t=(t+1)/2;
}
else
{
t/=2;
}
return t;
}
ll even(ll L,ll R)
{
ll t=R-L+1;
if(L%2==0&&R%2==0)
{
t=(t+1)/2;
}
else
{
t/=2;
}
return t;
}
void solve(ll x1,ll x2,ll y1,ll y2)
{
if(x1==x2&&y1==y2&&(x1+y1)&1)
{
calc(x1-1,y1);
calc(x1+1,y1);
calc(x1,y1-1);
calc(x1,y1+1);
assert(ans%2==0);
}
else
{
calc(x1,y1);
cnt=odd(x1,x2)*odd(y1,y2)+even(x1,x2)*even(y1,y2);
assert(ans%2==0);
}
}
int main()
{
freopen("zhengzhou.in","r",stdin);
freopen("zhengzhou.out","w",stdout);
read(n);
for(int i=0;i<n;++i)
{
ll x=read<ll>(),y=read<ll>();
::x[i]=x+y,::y[i]=x-y; // *2
}
sort(x,x+n);
sort(y,y+n);
ans=1e18;
solve(x[(n-1)/2],x[n/2],y[(n-1)/2],y[n/2]);
printf("%lld
%lld
",ans/2,cnt);
// fclose(stdin);
// fclose(stdout);
return 0;
}