问题陈述
您正在玩硬币拼图。这个谜题的规则如下:
桌子上有$N$ 硬币。第 $i$ 个硬币是一个半径为 $r_i$ 的圆,其中心最初位于 $(sx_i, sy_i)$。每个硬币也有一个目标位置:您应该移动第 $i$ 个硬币,使其中心位于 $(tx_i, ty_i)$。您可以一枚一枚地移动硬币,并且每个硬币最多只能移动一次。当你移动一枚硬币时,它必须沿着直线从初始位置移动到目标位置。此外,硬币不能相互碰撞,包括在移动过程中。
拼图的得分是您从初始位置移动到目标位置的硬币数量。您的任务是编写一个程序来确定给定谜题实例的最高分数。
输入
输入由单个测试用例组成,格式如下。
$N$ $r_{1}$ $sx_{1}$ $sy_{1}$ $tx_{1}$ $ty_{1}$ $\vdots$ $r_{N}$ $sx_{N}$ $sy_{N}$ $tx_{N}$ $ty_{N}$
第一行包含一个整数 $N$ ($1 \le N \le 16$),它是拼图中使用的硬币数量。 1{,}000$, $-1{,}000 \le sx_i, sy_i, tx_i, ty_i \le 1{,}000$, $(sx_i, sy_i) \neq (tx_i, ty_i)$)。 $(sx_i, sy_i)$ 是第 $i$ 个硬币的初始位置,$(tx_i, ty_i)$ 是第 $i$ 个硬币的目标位置。
您可以假设硬币在初始位置不接触或不相互重叠。您还可以假设即使每个硬币的半径改变 $10^{-5}$,最高分数也不会改变。
输出
在一行中打印给定拼图实例的最大分数。
示例输入 1
3 2 0 0 1 0 2 0 5 1 5 4 1 -10 -5 10
样本输入 1 的输出
2
示例输入 2
3 1 0 0 5 0 1 0 5 0 0 1 5 5 0 5
样本输入 2 的输出
3
示例输入 3
4 1 0 0 5 0 1 0 5 0 0 1 5 5 0 5 1 5 0 0 0
样本输入 3 的输出
0
注意
在第一个示例中,第三枚硬币无法移动,因为它受到其他两枚硬币的干扰。
示例 1. 初始位置
示例 1. 移动后