Submission #2855940

---

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

namespace std {
  template <> struct hash<P> {
    size_t operator()(P const& x) const {
      return hash<int64_t>()(x.first) ^ hash<int64_t>()(x.second);
    }
  };
}

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, unordred_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());

  ///////////////////////

  unordred_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

Compile Error

./Main.cpp:36:48: error: ‘unordred_map’ has not been declared
 auto count_points_in_rect(vector<P> const& vs, unordred_map<P, int>& counts, int i, int j) {
                                                ^
./Main.cpp:36:60: error: expected ‘,’ or ‘...’ before ‘<’ token
 auto count_points_in_rect(vector<P> const& vs, unordred_map<P, int>& counts, int i, int j) {
                                                            ^
./Main.cpp: In function ‘auto count_points_in_rect(const std::vector<std::pair<long int, long int> >&, int)’:
./Main.cpp:37:16: error: ‘i’ was not declared in this scope
   auto lt = vs[i];
                ^
./Main.cpp:38:18: error: ‘j’ was not declared in this scope
   auto rt = P{vs[j].first, vs[i].second};
                  ^
./Main.cpp:38:40: error: no matching function for call to ‘std::pair<long int, long int>::pair(<brace-enclosed initializer list>)’
   auto rt = P{vs[j].first, vs[i].second};
                                        ^
In file included from /usr/include/c++/5/bits/...