Codeforces-1486B Eastern Exhibition


Problem

Portal


Thoughts

这个就是货仓选址那个题的经典结论:取所有x的中位数,如果n是奇数那么中位数唯一;反之可以选中间两个数之间的任何一个位置.那么由于两个子问题相互独立,直接乘法原理统计方案数就可以了.


Accepted Code

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e6+10;

int x[N], y[N];

signed main()
{
#ifdef w
    freopen("out", "w", stdout);
#endif
    int T; cin >> T;
    while(T -- )
    {
        int n; cin >> n;
        for(int i = 1 ; i <= n ; i ++ ) cin >> x[i] >> y[i];
        sort(x+1, x+1+n), sort(y+1, y+1+n);
        if(n&1) puts("1");
        else cout << (x[n/2+1]-x[n/2]+1) * (y[n/2+1]-y[n/2]+1) << endl;
    }
    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
最大团算法 最大团算法
写在前面, 补图的最大独立集点数 = 原图的最大团点数。在原图中有的边在补图中都没有,原图的最大团的所有边去掉之后,其就是补图的最大独立集。 最大团一般图中的最大团问题写在前面,求最大团,我们用算法3,最快,极大团数量只能用算法1。
2021-04-15
Next 
Codeforces-1486A Shifting Stacks Codeforces-1486A Shifting Stacks
ProblemPortal Meaning给定一个序列,每次将第i个数-1,第i+1个数+1,问是否能够将其变成严格单调递增的序列。 Thoughts输出no的情况,当前数不够大,所以在前面我们尽可能的将当前数做到条件允许的最小值(0,
  TOC