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 |
|
|
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 |