Codeforces Gym101505G：Orchard Division（扫描线+线段树第k大）

题目链接

题意

给出一个m*m的地图，上面有n个点，现在需要用一个自定义面积的矩形笼罩住恰好n/2个点，并且这个矩形需要有一个点在至少一个角落上，问这个矩形最小的面积是多少。

思路

有点类似于扫描线。将y坐标离散化，沿着x轴扫过去，边加点边查找，注意这里一定要每次加一列（即x相同的时候要全加进去，不然找第k大的时候可能出错），每次查找的时候就找恰好第n/2大的y坐标，然后就可以得到面积了。

考虑到四个角都需要判定，一开始我写了四个又长又臭的函数，后来队友写了一个挺妙的Rotate()函数。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int INF = 0x3f3f3f3f;

const int N = 1e6 + 11;

const LL inf = 2e18;

#define lson l, m, rt<<1

#define rson m + 1, r, rt<<1|1

struct Node {

    int x, y;

} p[N];

int yy[N], cy, tree[N<<2], n, m, x, y;

LL ans;

bool cmp(const Node &a, const Node &b) {

    if(a.x == b.x) return a.y < b.y;

    return a.x < b.x;

}

void Rotate() {

    for(int i = 1; i <= n; i++) {

        x = p[i].x;

        p[i].x = m - p[i].y + 1;

        p[i].y = x;

    }

}

void build(int l ,int r, int rt) {

    tree[rt] = 0;

    if(l == r) return ;

    int m = (l + r) >> 1;

    build(lson); build(rson);

}

void update(int id, int w, int l, int r, int rt) {

    tree[rt] += w;

    if(l == r) return ;

    int m = (l + r) >> 1;

    if(id <= m) update(id, w, lson);

    else update(id, w, rson);

}

int query(int k, int l, int r, int rt) {

    if(tree[rt] < k) return -1;

    if(l == r) return tree[rt] == k ? yy[l] : -1;

    int m = (l + r) >> 1;

    if(tree[rt<<1] >= k) return query(k, lson);

    else return query(k - tree[rt<<1], rson);

}

void solve() {

    cy = 0;

    for(int i = 1; i <= n; i++) yy[++cy] = p[i].y;

    sort(yy + 1, yy + 1 + cy);

    cy = unique(yy + 1, yy + 1 + cy) - yy - 1;

    sort(p + 1, p + 1 + n, cmp);

    build(1, cy, 1);

    for(int i = 1; i <= n; ) {

        for(x = p[i].x ; i <= n && p[i].x == x; i++) {

            y = lower_bound(yy + 1, yy + 1 + cy, p[i].y) - yy;

            update(y, 1, 1, cy, 1);

        }

        if(i < n / 2) continue;

        int now = query(n / 2, 1, cy, 1);

        if(now == -1) continue;

        ans = min(ans, 1LL * x * now);

    }

    Rotate();

}

int main() {

    while(~scanf("%d%d", &m, &n)) {

        for(int i = 1; i <= n; i++) {

            scanf("%d%d", &p[i].x, &p[i].y);

            p[i].x++; p[i].y++;

        }

        if(n & 1) { puts("-1"); continue; }

        ans = inf;

        for(int i = 0; i < 4; i++) solve();

        if(ans == inf) ans = -1;

        printf("%lld\n", ans);

    }

    return 0;

}