题目链接

题目大意

给定n个点，找到若干个中心，使得中心到各个点的曼哈顿距离之和最小。输出中心个数

解题思路

首先，假设中心横坐标首先选在x_1（假设已经从小到大排序过），那么X方向上的曼哈顿距离之和sum = \sum_{i = 2}^{n}(x_i-x_1)。

假设我们横坐标移动到x_2，那么此时 sum相对于上一步，相当于减去\sum_{i = 3}^{n}(x_2-x_1)，加上\sum_{i = 1}^{1}(x_2-x_1)

假设我们横坐标移动到x_3，那么此时 sum相对于上一步，相当于减去\sum_{i = 4}^{n}(x_3-x_2)，加上\sum_{i = 1}^{2}(x_3-x_2)

… …

假设我们横坐标移动到x_p，那么此时 sum相对于上一步，相当于减去\sum_{i = p+1}^{n}(x_p-x_{p-1})，加上\sum_{i = 1}^{p-1}(x_p-x_{p-1})

不难发现，当n较大时，sum起初下降，因为减少量多于增加量；与之对应，sum最终会上升，因为反方向而言，增加量多于减少量。因此，sum是一个单峰函数，先下降，再上升。

不妨将下标取中位数，mid。

假如p=mid，若挪至p=mid+1，则减去\sum_{i = mid+2}^{n}(x_{mid+1}-x_{mid})，加上\sum_{i = 1}^{mid}(x_{mid+1}-x_{mid}) 显然，此时增加量更多，sum将会增大

若挪至p=mid-1，亦然，增加量更多，sum增大。

综上所述，当取中位数时，总曼哈顿距离最小，同理适用于Y方向。

还有一点小问题：

若n为奇数，则X方向Y方向的中位数x_{mid}和y_{mid}所在位置即为中心。显然，中心有且仅有一个。

若n为偶数，中心选取在x_{\lfloor mid \rfloor} 和x_{\lceil mid \rceil}之间且y不变（定义double mid=(l+r)/2)时，sum值不变。同理，在y_{\lfloor mid \rfloor}和y_{\lceil mid \rceil}之间且x不变时，sum值不变

因此，在x_{\lfloor mid \rfloor} – x_{\lceil mid \rceil} ，y_{\lfloor mid \rfloor} – y_{\lceil mid \rceil}之间的区域，均可以为中心。

由于c++实际上进行整数除法时，舍去小数位（mid即向下取整）。因此，向上取整可写为mid+1【详见代码】

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+7;
int T;
int n,m;
int a[N];
int b[N];

signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
        }
        if(n%2 == 1){
            cout<<1<<endl;
            continue;
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        int mid=n/2;
        cout<<(a[mid+1]-a[mid]+1)*(b[mid+1]-b[mid]+1)<<endl;
    }
    return 0;
}