AtCoder Beginner Contest 075 D問題

AtCoder Beginner Contest 075 - AtCoder のD問題を解きました．

平面上にn個の点と自然数kが与えられたときに，ある決められた幾何形状でk個以上の点を含むものの中で面積最小のものを見つける問題は k-enclosing problem と呼ばれています．一般に，幾何形状としては円板や正方形などがあり，今回の問題では軸平行な矩形(parallel rectangle)を見つける問題となります．例えば簡単な特殊問題として，kをnとして幾何形状を凸多角形とした場合には凸法を求める問題となり 時間で計算できます．
今回のD問題は，parallel rectangle の k-enclosing problem ですが，公式の解説には愚直な のアルゴリズムが紹介されています．また，二次元累積和を用いることで に計算時間を減らすことができるらしいです．

関連研究として 時間のアルゴリズムがあります．
Many points in small boxes
論文紹介しようかと思いましたが のアルゴリズムが思いつく(研究室の後輩に聞きました)ので のアルゴリズムを説明します．良い上界の決定性のアルゴリズムがあるのか，下界はどれぐらいなのかはさらっと調べて見つからなかったので分かる方は教えてくださると嬉しいです．

[Problem D. Axis-Parallel Rectangle]

問題文

D - Axis-Parallel Rectangle

方針

前もって与えられた点をx座標の昇順でソートします．次に，解の候補となる軸平行な矩形の上辺と下辺を全通り試します．矩形の上辺と下辺が固定されたときに，候補となるk個以上の点を含む矩形の左辺と右辺を尺取り法で探索して面積が最小のものを見つけます．下の図の番号はx座標で昇順にソートしたときの番号で，赤色の点が上辺と下辺を固定したときの考慮する点です．尺取り法では左からk個の点を含む矩形から始めて右にスライドさせます．
前処理のソートは 時間，矩形の上辺と下辺の候補の数が で，その中で尺取り法で なので全体で 時間となります．

実装

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using Point = pair<int, int>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, k;

    cin >> n >> k;
    vector<Point> p(n);
    vector<int> y(n), idx(n);
    int size;

    for (int i = 0; i < n; ++i) {
        cin >> p[i].first >> p[i].second;
        y[i] = p[i].second;
    }

    sort(p.begin(), p.end());
    sort(y.begin(), y.end());

    ll min_area = (ll)(y[n - 1] - y[0]) * (ll)(p[n - 1].first - p[0].first);
    for (int by = 0; by < n; ++by) {
        for (int ty = by + 1; ty < n; ++ty) {
            size = 0;
            for (int i = 0; i < n; ++i)
                if (y[by] <= p[i].second && p[i].second <= y[ty])
                    idx[size++] = i;

            int lb = 0;
            while (lb + k - 1 < size) {
                min_area = min(min_area, (ll)(y[ty] - y[by]) * (ll)(p[idx[lb + k - 1]].first - p[idx[lb]].first));
                ++lb;
            }
        }
    }

    cout << min_area << endl;

    return 0;
}