目次

• 問題
  • 入力
  • 出力
• 解説
• 計算量
• 解答

# 問題

https://atcoder.jp/contests/abc091/tasks/arc092_a

平面上に複数の点を与えられて、ある条件を満たすペアが最大でいくつ作れるかを答える問題です.

# 入力

N
a_x_1 a_y_1
a_x_2 a_y_2
...
a_x_N a_y_N
b_x_1 b_y_1
b_x_2 b_y_2
...
b_x_N b_y_N

• N - 1以上100以下の整数で続くN行にAに属する点の座標が、さらにそれに続くN行にBに属する点の座標が与えられます.
• a_x_i, a_y_i - Aに属する点の座標(a_x_i, a_y_i)
• b_x_i, b_y_i - Bに属する点の座標(b_x_i, b_y_i)

# 出力

Aに属する点aのxとyがともにBに属する点bよりも小さい時にそのaとbをペアに出来ます.
一度ペアに使った点は他のペアには使用できません.
最大でいくつのペアを作ることが出来るか答える問題です.

# 解説

Bは$x$座標が小さい方から順にチェックします.
Aをすべてチェックし、条件を満たすAが１つしかない場合はそのAとペアにします.
条件を満たすAが１つもない場合はそのBではペアは作れません.
条件を満たすAが複数ある場合は$y$座標が最も大きいものを選択すれば良いです.
Aは条件を満たしていてもすでに使われていたら使えないことに注意が必要です.

# 計算量

$O(N^2)$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

struct Point {
  Int x, y;
  Point(Int x, Int y): x(x), y(y) {}
  Point(): x(0), y(0) {}

  bool operator< (const Point &p1) {
    return x < p1.x && y < p1.y;
  }
};
ostream & operator << (ostream & out, Point const & v) {
  out << "Point(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Point & v) {
  Int x, y;
  in >> x; in >> y; v.x = x; v.y = y;
  return in;
}

bool compX (const Point &p1, const Point &p2) {
  return p1.x < p2.x;
}

bool compY (const Point &p1, const Point &p2) {
  return p1.y < p2.y;
}

#define MAX_N 100
Int N;
vector<Point> red, blue;
vector<bool> rused(MAX_N, false);

void input() {
  cin >> N;
  Point p_;
  loop(n,0,N) {
    cin >> p_;
    red.push_back(p_);
  }
  loop(n,0,N) {
    cin >> p_;
    blue.push_back(p_);
  }
}

void solve() {
  sort(span_all(red), compY);
  sort(span_all(blue), compX);

  Int count = 0;
  loop(b_i, 0, blue.size()) {
    Int max_ = -1;
    loop(r_i, 0, red.size()) {
      if (!rused.at(r_i) && red.at(r_i) < blue.at(b_i)) max_ = r_i;
    }

    if (max_ > -1) {
      rused.at(max_) = true;
      count++;
    }
  }
  cout << count << endl;
}

int main() {
  input();
  solve();
  return 0;
}