CF1486B Eastern Exhibition 题解

· · 题解

考虑到 x 和 y 是两个互不影响的量。分开来考虑。

假设考虑第一维，降维抽象成一个数轴，上面有若干点。你需要选取一个点，使得所有点到这个点的距离和最小。求可以选取的点的范围。

这是一个初中常见的问题，主要是研究绝对值性质与几何结合所用。这里不拓展只给出结论。选取的范围是，如果 n 是奇数，则为 n 个点的中位数的对应点；否则为两个中位数形成的闭区间。

那么，这个问题就很显然易见了。如果 n 是奇数，答案为 1；否则就将 x,y 坐标分别排序，求其中位数选取的范围区间包含的整数点个数乘积之和。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL x[1005],y[1005],n;
int main(){
    LL T;
    scanf("%lld",&T);
    while(T-->0)
    {
        scanf("%lld",&n);
        for(LL i=1;i<=n;++i)    scanf("%lld %lld",&x[i],&y[i]);
        if(n&1)
        {
            puts("1");
            continue;
        }
        sort(x+1,x+1+n),sort(y+1,y+1+n);
        LL sx=x[n/2+1]-x[n/2]+1,sy=y[n/2+1]-y[n/2]+1;
        printf("%lld\n",sx*sy);
    }
    return 0;
}