21. Mr. Sloth and his party

单点时限: 1.0 sec

内存限制: 256 MB

树獭先生一直热衷于舞蹈。前几天,他刚学会了一种新的舞蹈「法国传统舞蹈」。为了大显身手,他特地准备了一场舞会,并请来了他的朋友们。

「法国传统舞蹈」是一种交谊舞,因此会有 $n$ 位树獭叔叔 $n$ 位树獭姐姐一起来到舞会。为了增加舞会的趣味性,规定:每一次舞曲响起时,每一位树獭叔叔和树懒姐姐都必须找到一位舞伴(必须是异性),与 TA 完成接下来的舞蹈。在一支舞曲结束后,舞伴之间会相互交换位置。另外,任意两个位置之间都有一种名叫荷尔蒙的吸引力存在,只有在这种吸引力存在时,两个位置的树獭才能一起跳舞;而且在跳过一次舞后,这两个位置之间的荷尔蒙就会永久失效。

然而,两首乐曲之间的间隔是很短的。因此,每一位树獭叔叔/姐姐都只能在与 TA 距离不超过 $r$ 的范围内寻找下一位舞伴。

给定每一位树獭叔叔/姐姐开始时在舞厅中的位置,舞会的负责獭想知道,树獭叔叔、姐姐们最多能一起跳完多少支舞曲呢?

输入格式

不超过 $30$ 组测试数据。对于每组数据:

第一行是两个整数 $n$ $(1 \leq n \leq 50)$, $r$ $(1 \leq r \leq 10^9)$。

之后 $n$ 行,每行2个整数 $x_i$, $y_i$ $(0 \leq x_i, y_i \leq 10^9)$,表示第 $i$ 个树獭叔叔的位置。

再之后 $n$ 行,每行2个整数 $p_i$, $q_i$ $(0 \leq p_i, q_i \leq 10^9)$,表示第 $i$ 个树獭姐姐的位置。

同一个位置不会出现两个树獭。

输出格式

输出一个整数,表示最多能完成的舞曲数量。

样例

Input
1 5
0 0
4 3
2 2
0 0
2 0
1 1
3 1
3 100
0 0
0 1
0 2
1 0
1 1
1 2
Output
1
1
3

提示

第一组样例:一个叔叔在 $(0, 0)$,一个姐姐在 $(4, 3)$,距离为 $\sqrt{(4-0)^2+(3-0)^2} = 5 \leq 5$。所以总共一种配对方案,所以只能跳一场舞。

第二组样例:两个叔叔分别在 $(0, 0)$、$(2, 0)$,一个姐姐分别在 $(1, 1)$、$(3, 1)$。第一场舞在叔叔1号和姐姐1号、叔叔2号与姐姐2号之间进行;然后他们互换位置,两个叔叔分别在 $(1, 1)$、$(3, 1)$,两个姐姐分别在 $(0, 0)$、$(2, 0)$。这时,叔叔1号想和漂亮哒姐姐2号跳舞(确实是可以的),但对于叔叔2号和姐姐1号,他们的距离为 $\sqrt{10} > 2$。所以,在第二场中,不是每一位叔叔和姐姐都能找到自己的舞伴,所以不能进行。

第三组样例:显然任意一对舞伴都能够跳舞。但注意到荷尔蒙是有限的,到最后会出现两个树獭能跳舞,但他们所在的位置之间缺少荷尔蒙的情况。所以只能有 $3$ 场。

4 人解决,10 人已尝试。

11 份提交通过,共有 44 份提交。

8.4 EMB 奖励。

创建: 7 年,7 月前.

修改: 6 年,10 月前.

最后提交: 2 月,3 周前.

来源: 2017 CCCC 选拔

题目标签