3403. 不死の宝石

单点时限: 2.0 sec

内存限制: 256 MB

曾经有一位贵族爱上了一个勇敢的公主,在一个贫穷的国家的坟墓里求婚。公主出现了贵族存在的条件。这样的条件是带来了大量名为「不死的宝石」的宝石。一个不朽的宝石是一个非常罕见的宝石,只能在一个山的某个地方被采取。此外,由于它非常脆弱,所以需要采取一种特殊的方法来收集。

不朽宝石具有圆形形状,二维空间中有多个宝石。为了拿这个宝石,有必要用特殊的金属棒吸它们。金属条是无限长的直线,厚度可忽略不计。每个宝石都具有不同强度的磁力,并且如果金属足够接近于其磁力,宝石被吸附。具体地说,当金属和宝石表面之间的距离为 $d$ 时,宝石的磁力强度为 $m$ ($0 \le d \le m$)。如果是这样,宝石被金属吸附。相反,如果金属棒和宝石与其磁力分离,则不能被吸附。此外,即使一根棍子穿过宝石甚至一点点,它也不会被吸附,因为宝石被破坏了。

我们来看一个例子。下图是放置在二维空间中的宝石的示例。宝石 $1$ 至宝石 $6$,磁力分别为 $1,0,1,1,1,2$。

图:宝石安排示例

以下是与上述附图相比设置金属棒的例子。吸附宝石的结果也列于表中。在这个例子中,宝石 3 远离磁力的可达范围,并且由于宝石 4 被杆穿透,所以它不能被吸附,而剩下的四个可被吸附。

图:金属棒布置示例

编号 磁力 距离 可以否
宝石1 1 约 0.21 可以
宝石2 0 0 可以
宝石3 1 约 5.37 不能
宝石4 1 穿透 不能
宝石5 1 约 0.97 可以
宝石6 2 约 0.53 可以

贵族倾倒了所有的财富,拼命地寻找一个特殊的金属棒。然而,由于这种金属也是非常有价值的,只有一个最终可用。因此只有一次吸附的机会。

你是一位为某位贵族服务的程序员。你的工作是写一个程序,要求在给定的二维宝石放置时安排金属棒,最多可以吸收多少宝石。

输入格式

输入由多个数据集组成,一个数据集的格式如下:

$n \
x_1 \ y_1 \ r_1 \ m_1 \
x_2 \ y_2 \ r_2 \ m_2 \
\vdots \
x_N \ y_N \ r_N \ m_N$

数据集的第一行表示宝石数量 $N$ ($1 \le N \le 50$)。

在以下 $N$ 行的每一行中,有四个整数 $x_i,y_i,r_i,m_i$ ($-1000 \le x_i,y_i \le 1000,1 \le i \le 100, 0 \le mi \le 100$),表示宝石的位置和大小,和磁力。也就是说,有一个圆形宝石的中心是 $(x_i,y_i)$,半径是 $r_i$,它的磁力是 $m_i$。宝石从不重叠。

输入的结尾由只包含 0 的行表示。

输出格式

对于每个数据集,输出一行可以一次吸收的最大数量的宝石。

样例

Input
6
-2 -2 1 1
2 2 2 0
5 7 1 1
8 0 3 1
13 4 1 1
16 1 1 2
3
0 0 2 1
10 0 2 1
0 10 2 1
3
0 0 2 1
10 0 2 1
0 6 2 1
3
0 0 2 1
10 0 2 1
0 4 2 1
1
0 0 1 1
0
Output
4
2
3
3
1

8 人解决,20 人已尝试。

10 份提交通过,共有 121 份提交。

7.8 EMB 奖励。

创建: 7 年,1 月前.

修改: 7 年,1 月前.

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

来源: ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2010

题目标签