题目详情题解（0）讨论（0）提交记录（0）

AT_arc092_a.[ABC091C] 2D Plane 2N Points

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二维平面上有 NN 个红点和 NN 个蓝点。第 ii 个红点的坐标为 (ai, bi)(a_i,\ b_i)，第 ii 个蓝点的坐标为 (ci, di)(c_i,\ d_i)。

当且仅当红点的 xx 坐标小于蓝点的 xx 坐标，且红点的 yy 坐标也小于蓝点的 yy 坐标时，这个红点和蓝点可以组成一个“好朋友”配对。

你最多可以组成多少对好朋友配对？注意，每个点最多只能属于一个配对。

输入格式

输入以如下格式从标准输入给出。

NN
a1a_1 b1b_1
a2a_2 b2b_2
⋮\vdots
aNa_N bNb_N
c1c_1 d1d_1
c2c_2 d2d_2
⋮\vdots
cNc_N dNd_N

输出格式

输出好朋友配对的最大数量。

输入输出样例

  • 输入#1

    3
2 0
3 1
1 3
4 2
0 4
5 5

    输出#1

    2

  • 输入#2

    3
0 0
1 1
5 2
2 3
3 4
4 5

    输出#2

    2

  • 输入#3

    2
2 2
3 3
0 0
1 1

    输出#3

    0

  • 输入#4

    5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

    输出#4

    5

  • 输入#5

    5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

    输出#5

    4

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤1001 \leq N \leq 100。
  • 0≤ai,bi,ci,di<2N0 \leq a_i, b_i, c_i, d_i < 2N。
  • a1,a2,…,aN,c1,c2,…,cNa_1, a_2, \ldots, a_N, c_1, c_2, \ldots, c_N 均互不相同。
  • b1,b2,…,bN,d1,d2,…,dNb_1, b_2, \ldots, b_N, d_1, d_2, \ldots, d_N 均互不相同。

样例解释 1

例如，可以将 (2,0)(2, 0) 与 (4,2)(4, 2) 配对，将 (3,1)(3, 1) 与 (5,5)(5, 5) 配对。

样例解释 2

例如，可以将 (0,0)(0, 0) 与 (2,3)(2, 3) 配对，将 (1,1)(1, 1) 与 (3,4)(3, 4) 配对。

样例解释 3

有时也可能无法组成任何配对。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页