21. Mr. Sloth and his party

单点时限: 1.0 sec

内存限制: 256 MB

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

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

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

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

输入格式

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

第一行是两个整数 ,

之后 行,每行2个整数 , ,表示第 个树獭叔叔的位置。

再之后 行,每行2个整数 , ,表示第 个树獭姐姐的位置。

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

输出格式

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

样例

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

提示

第一组样例:一个叔叔在 ,一个姐姐在 ,距离为 。所以总共一种配对方案,所以只能跳一场舞。

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

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

3 人解决,8 人已尝试。

8 份提交通过,共有 36 份提交。

8.9 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年前.

最后提交: 1 年,9 月前.

来源: 2017 CCCC 选拔

题目标签