Submission #2855948
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }
template<class T> istream& operator>> (istream& ist, pair<T, T>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
typedef long long ll;
int64_t const inf = std::numeric_limits<int64_t>::max();
using P = pair<int64_t, int64_t>;
int N, K;
auto in_left_cornered_rect(int x, int y, int lx, int ly) {
return lx <= x && ly <= y;
}
auto count_points_in_rect(vector<P> const& vs, map<P, int>& counts, int i, int j) {
auto lt = vs[i];
auto rt = P{vs[j].first, vs[i].second};
auto lb = P{vs[i].first, vs[j].second};
auto rb = vs[j];
if (counts.find(rt) == counts.end()) return 0;
if (counts.find(lb) == counts.end()) return 0;
return counts[lt] - counts[rt] - counts[lb] + counts[rb];
}
int main() {
cin >> N >> K;
vector<P> in;
rep(i, N) {
int x, y; cin >> x >> y;
in.emplace_back(x, y);
}
// 点の座標集合の直積
vector<P> vs = in;
rep(i, N) rep(j, N) {
vs.emplace_back(min(in[i].first, in[j].first), min(in[i].second, in[j].second));
vs.emplace_back(max(in[i].first, in[j].first) + 1, min(in[i].second, in[j].second));
vs.emplace_back(min(in[i].first, in[j].first), max(in[i].second, in[j].second) + 1);
vs.emplace_back(max(in[i].first, in[j].first) + 1, max(in[i].second, in[j].second) + 1);
}
sort(vs.begin(), vs.end());
vs.erase(unique(vs.begin(), vs.end()), vs.end());
///////////////////////
map<P, int> counts;
for (auto const& corner: vs) {
rep(i, N) {
counts[corner] += !!in_left_cornered_rect(in[i].first, in[i].second, corner.first, corner.second);
}
}
///////////////////////
int64_t min_rect = inf;
rep(i, vs.size()) rep(j, vs.size()) {
if (!(vs[i].first < vs[j].first && vs[i].second < vs[j].second)) continue;
if (count_points_in_rect(vs, counts, i, j) >= K) {
auto W = vs[j].first - vs[i].first - 1;
auto H = vs[j].second - vs[i].second - 1;
minimize(min_rect, (int64_t)W * H);
}
}
cout << min_rect << "\n";
}
Submission Info
Submission Time |
|
Task |
D - Axis-Parallel Rectangle |
User |
motxx |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2752 Byte |
Status |
AC |
Exec Time |
199 ms |
Memory |
576 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 |
2 ms |
380 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
7 ms |
256 KB |
subtask_1_10.txt |
AC |
27 ms |
384 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_12.txt |
AC |
8 ms |
384 KB |
subtask_1_13.txt |
AC |
9 ms |
384 KB |
subtask_1_14.txt |
AC |
1 ms |
256 KB |
subtask_1_15.txt |
AC |
2 ms |
256 KB |
subtask_1_16.txt |
AC |
197 ms |
572 KB |
subtask_1_17.txt |
AC |
198 ms |
572 KB |
subtask_1_18.txt |
AC |
198 ms |
572 KB |
subtask_1_19.txt |
AC |
199 ms |
572 KB |
subtask_1_2.txt |
AC |
5 ms |
256 KB |
subtask_1_20.txt |
AC |
197 ms |
572 KB |
subtask_1_21.txt |
AC |
1 ms |
256 KB |
subtask_1_22.txt |
AC |
12 ms |
384 KB |
subtask_1_23.txt |
AC |
198 ms |
572 KB |
subtask_1_24.txt |
AC |
194 ms |
572 KB |
subtask_1_3.txt |
AC |
4 ms |
256 KB |
subtask_1_4.txt |
AC |
95 ms |
512 KB |
subtask_1_5.txt |
AC |
197 ms |
576 KB |
subtask_1_6.txt |
AC |
63 ms |
512 KB |
subtask_1_7.txt |
AC |
50 ms |
512 KB |
subtask_1_8.txt |
AC |
39 ms |
504 KB |
subtask_1_9.txt |
AC |
137 ms |
512 KB |