噴水裝置（一）

時間限製：3000 ms | 內存限製：65535 KB

難度：3

描述

現有一塊草坪，長為20米，寬為2米，要在橫中心線上放置半徑為Ri的噴水裝置，每個噴水裝置的效果都會讓以它為中心的半徑為實數Ri(0<Ri<15)的圓被濕潤，這有充足的噴水裝置i（1<i<600)個，並且一定能把草坪全部濕潤，你要做的是：選擇盡量少的噴水裝置，把整個草坪的全部濕潤。

輸入

第一行m表示有m組測試數據
每一組測試數據的第一行有一個整數數n，n表示共有n個噴水裝置，隨後的一行，有n個實數ri，ri表示該噴水裝置能覆蓋的圓的半徑。

輸出

輸出所用裝置的個數

樣例輸入

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

樣例輸出

2
5

01.#include <iostream>

02.#include <cmath>

03.#include <algorithm>

04.using namespace std;

05.

06.int main()

07.{

08.int t;

09.cin >> t;

10.

11.while (t--)

12.{

13.int n, i;

14.cin >> n;

15.

16.float *r = new float[n];

17.for (i = 0; i < n; i++)

18.cin >> r[i];

19.sort(r, r+n, greater<float>());//指定從大到小排序

20.//for (i = 0; i < n; i++)

21.// cout << r[i] << " ";

22.//cout << endl;

23.

24.double width = 0;

25.i = 0;

26.while (width - 20 < 1e-9 && i < n)

27.{

28.width += sqrt(r[i] * r[i] - 1 * 1) * 2;

29.i++;

30.}

31.cout << i << endl;

32.

33.delete [] r;

34.}

35.return 0;

36.}

最後更新：2017-04-02 15:14:53

噴水裝置（一）