题意

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\n%lld\n",ans/2,cnt);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

巴特西

test20181015 B 君的第三题

题意