AT_joisc2009_starry_sky 星空 (Starry Sky)

题目描述

### 题目背景 日本天文台协会 `(Japan Observatory Institution)` 最近安装了高性能天文望远镜。`JOI` 通过向大众广泛宣传该天体望远镜的性能,提高了 `JOI` 的知名度。根据长时间会议的结果,展示这个天文望远镜性能的最有效的效果的宣传方法是,尽可能多地拍摄充分闪耀的星星的图像,广泛地向公众公开。 但是,宇宙是广阔的。要想把一切都收在一张图像里,那么每一颗星星的光辉就不能充分表示。另一方面,该天文望远镜有着高性能。通过放大拍摄星空,每颗星星都十分耀眼,可以作为多状态拍摄。但是通过放大,就能进入图像中留下的星星的数量会减少。最多可以把几颗足够耀眼的星星收进图像里? 当关于每颗星星的下一个信息被给出的时候,足够闪耀的星星将被收录在图像中。 请编写程序,计算能做到的星星的最大数量。 - 星星的位置是 $(x,y)$。 - 用这个天体望远镜拍摄的图像是每个边平行于 $x$ 轴与 $y$ 轴的任意大小的正方形。 - 为表示恒星的光度和达到充分发光状态所需的放大倍率的关系,每次给出在充分发光的状态下拍摄所需的正方形区域的边长 $L$。 如果所拍摄的正方形区域的边长不大于 $L$,那么这颗星星就会进入图像中。在正方形区域的边缘上即使有,也不能拍摄成十分耀眼的星星。 任何不同的两颗星,彼此的 $x$ 坐标、$y$ 坐标、$L$的值都是唯一的。

输入格式

第一行中,输入表示星星数量的整数 $n$。 接下来的 $n$行表示星星的数据。接下来 $n$ 行,每行有三个整数 $x_i,y_i,L_i$ 。 给出星星的 $x,y$ 坐标,以及表示在充分发光的状态下可以拍摄的正方形区域的边长的最大值。

输出格式

用一行输出可以拍摄到的耀眼的星星的最大数 $15\%$ 的数据保证 $n\le100$; $25\%$ 的数据保证 $n\le400$; $35\%$ 的数据保证 $n\le700$; $50\%$ 的数据保证 $n\le1000$。 $100\%$ 的数据保证 $n\le4000$,$ x_i,y_i,L_i\le10^9$。 另外,$20\%$ 的数据保证 $x_i,y_i,L_i\le1000$。 #### 样例 $1$ 输入 ``` 4 1 2 6 4 3 3 3 1 4 5 5 2 ``` 输出 ``` 3 ``` #### 样例 $2$ 输入 ``` 5 11 6 7 12 13 8 15 16 18 2 2 13 3 4 11 ``` 输出 ``` 2 ```