8 人解决,20 人已尝试。
10 份提交通过,共有 121 份提交。
7.8 EMB 奖励。
单点时限: 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
的行表示。
对于每个数据集,输出一行可以一次吸收的最大数量的宝石。
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
4 2 3 3 1
8 人解决,20 人已尝试。
10 份提交通过,共有 121 份提交。
7.8 EMB 奖励。
创建: 7 年,2 月前.
修改: 7 年,2 月前.
最后提交: 5 月,3 周前.
来源: ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2010