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
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
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 |