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