Submission #2855238


Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <functional>
using namespace std;
#define pb          emplace_back
#define fi          first
#define se          second
#define show(...)   fprintf(stderr, __VA_ARGS__ )
#define outl(x)     cout << (x) << '\n'
#define rep(i,n)    for(int i=0; i<(n); ++i)
#define ALL(x) x.begin(), x.end()
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
inline bool inside(int x, int y, int W, int H) { return x>=0 && y>=0 && x<W && y<H; }
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
constexpr int       INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int dx[] = {1, 0, -1, 0};
constexpr int dy[] = {0, 1, 0, -1};

/*
map<int, ll> mp[55];
int slv(int idx, int minx, int miny, int maxx, int maxy, int S)
{

}
*/

int N, K;
ll x[55], y[55];

int countRectInnerPoint(ll minX, ll minY, ll maxX, ll maxY)
{
    int cnt = 0;
    rep(i, N) {
        if (x[i] >= minX
                && x[i] <= maxX
                && y[i] >= minY
                && y[i] <= maxY) {

            ++cnt;
        }
    }
    return cnt;
}


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

    ll minX, minY, maxX, maxY;

    cin >> N >> K;

    rep(i, N) {
        cin >> x[i] >> y[i];
    }

    ll ans = LINF;

    // i,k = x   j,l = y
    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            for (int k=i+1; k<N; ++k) {
                for (int l=j+1; l<N; ++l) {
                    minX = min(x[i], x[k]);
                    maxX = max(x[i], x[k]);
                    minY = min(y[j], y[l]);
                    maxY = max(y[j], y[l]);
                    if (countRectInnerPoint(minX, minY, maxX, maxY) >= K) {
                        ans = min(ans, (maxX-minX) * (maxY - minY));
                    }
                }
            }
        }
    }

    outl(ans);

}

Submission Info

Submission Time
Task D - Axis-Parallel Rectangle
User Arumakan1727
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2222 Byte
Status AC
Exec Time 139 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 15 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 5 ms 256 KB
subtask_1_14.txt AC 1 ms 256 KB
subtask_1_15.txt AC 2 ms 256 KB
subtask_1_16.txt AC 135 ms 256 KB
subtask_1_17.txt AC 136 ms 256 KB
subtask_1_18.txt AC 138 ms 256 KB
subtask_1_19.txt AC 139 ms 256 KB
subtask_1_2.txt AC 3 ms 256 KB
subtask_1_20.txt AC 138 ms 256 KB
subtask_1_21.txt AC 1 ms 256 KB
subtask_1_22.txt AC 6 ms 256 KB
subtask_1_23.txt AC 136 ms 256 KB
subtask_1_24.txt AC 135 ms 256 KB
subtask_1_3.txt AC 2 ms 256 KB
subtask_1_4.txt AC 60 ms 256 KB
subtask_1_5.txt AC 121 ms 256 KB
subtask_1_6.txt AC 39 ms 256 KB
subtask_1_7.txt AC 30 ms 256 KB
subtask_1_8.txt AC 22 ms 256 KB
subtask_1_9.txt AC 93 ms 256 KB