A204.Gold King洒洒水

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

青青草原遇到了十年来的第一次干旱,水成了最宝贵的资源。GoldKingGold King 家的农场需要水来浇灌,一开始 GoldKingGold King 挺勤快的,亲力亲为,但是这个干旱好像遥遥无期,于是 GoldKingGold King 开始了一番骚操作。
$Gold King $ 家的农场长为 2020 米,宽为 22 米,为了节约用水,在横中心线上放置半径为 RiR_i 的喷水装置,每个喷水装置的效果都会让以它为中心的,半径为实数 RiR_i(0<Ri<150<R_i<15) 的圆范围湿润,GoldKingGold King购买了充足的喷水装置 ii1<i<6001<i<600)个,并且一定能把农场全部湿润,但是怎样选择尽量少的喷水装置,把整个农场全部喷洒湿润,GoldKingGold King 犯起了难。

输入格式

第一行 mm 表示有 m(0<m<15)m(0<m<15) 组测试数据。

每一组测试数据的第一行有一个整数数 nnnn 表示共有 nn 个喷水装置。

随后的一行,有 nn 个实数 rir_irir_i表示该喷水装置能覆盖的圆的半径。

输出格式

输出所用装置的个数。

输入输出样例

  • 输入#1

    2
    5
    2 3.2 4 4.5 6 
    10
    1 2 3 1 2 1.2 3 1.1 1 2

    输出#1

    2
    5

说明/提示

0<Ri<15,1<i<6000<Ri<15,1<i<600

首页