Submission #2855299


Source Code Expand

// finish date: 2018/07/16
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>>
        vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>>
        vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


struct zahyou {
    int x, y;

    bool operator<(const zahyou &another) const {
        //メンバ変数であるnum1で比較した結果を
        //この構造体の比較とする
        return x < another.x;
    }

};

int main() {
    int N, K;
    cin >> N >> K;
    vi x(N), y(N);
    rep(i, N) cin >> x[i] >> y[i];
    int cnt;
    int cx1, cx2;
    int cy1, cy2;
    ll ans = LONG_LONG_MAX;
    rep(xi, N) {
        FOR(xj, xi + 1, N) {
            rep(yi, N) {
                FOR(yj, yi + 1, N) {
                    cnt = 0;
                    cx1 = min(x[xi], x[xj]);
                    cx2 = max(x[xi], x[xj]);
                    cy1 = min(y[yi], y[yj]);
                    cy2 = max(y[yi], y[yj]);
                    rep(i, N) {
                        if ((cx1 <= x[i] && x[i] <= cx2) && (cy1 <= y[i] && y[i] <= cy2)) cnt++;
                    }
                    if (cnt >= K) {
                        ans = min(ans, (ll) (cx2 - cx1) * (cy2 - cy1));
                    }
                }
            }
        }
    }
    cout << ans << endl;


    return 0;
}

Submission Info

Submission Time
Task D - Axis-Parallel Rectangle
User TASSAN
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1971 Byte
Status AC
Exec Time 116 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 27
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_1.txt AC 3 ms 256 KB
subtask_1_10.txt AC 12 ms 256 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_12.txt AC 4 ms 256 KB
subtask_1_13.txt AC 4 ms 256 KB
subtask_1_14.txt AC 1 ms 256 KB
subtask_1_15.txt AC 1 ms 256 KB
subtask_1_16.txt AC 114 ms 256 KB
subtask_1_17.txt AC 116 ms 256 KB
subtask_1_18.txt AC 114 ms 256 KB
subtask_1_19.txt AC 115 ms 256 KB
subtask_1_2.txt AC 2 ms 256 KB
subtask_1_20.txt AC 115 ms 256 KB
subtask_1_21.txt AC 1 ms 256 KB
subtask_1_22.txt AC 5 ms 256 KB
subtask_1_23.txt AC 114 ms 256 KB
subtask_1_24.txt AC 114 ms 256 KB
subtask_1_3.txt AC 2 ms 256 KB
subtask_1_4.txt AC 51 ms 256 KB
subtask_1_5.txt AC 102 ms 256 KB
subtask_1_6.txt AC 32 ms 256 KB
subtask_1_7.txt AC 25 ms 256 KB
subtask_1_8.txt AC 19 ms 256 KB
subtask_1_9.txt AC 77 ms 256 KB