正文

test20181015 B 君的第三题

IP云
IP云V管理员/3 阅读
09/16
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意

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。

但是有问题，就是选出来的在曼哈顿距离下是整点，但在切比雪夫距离下不一定是整点。

所以需要分类讨论。

  1. 能选的只有一个点，但这个点不是整点，所以要想四周抖动。
  2. 能选的是一个范围，所以要奇偶配对。

代码

#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\n%lld\n",ans/2,cnt);
// fclose(stdin);
// fclose(stdout);
return 0;
}