4 人解决,10 人已尝试。
11 份提交通过,共有 44 份提交。
8.4 EMB 奖励。
单点时限: 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$ 个树獭姐姐的位置。
同一个位置不会出现两个树獭。
输出一个整数,表示最多能完成的舞曲数量。
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
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 奖励。