# Uva 10382: Watering Grass
###### tags: `貪心法` `區間覆蓋`

> 一個長為 $l$, 寬為 $w$ 的田地有 $n$ 個灑水器,
> 給定每個灑水器的位置, 以及其噴灑半徑 $r$,
> 試計算出能噴到整個田地灑水器的最小數量,
> 若無法完全覆蓋，則輸出 $-1$，反之輸出最小數量。

**Source:** [題目傳送門](https://vj.z180.cn/b569d6cab94c895b00989e543f81e077?v=1594628801)

{%pdf https://vj.z180.cn/b569d6cab94c895b00989e543f81e077?v=1595085640 %}

---

## *Original*

### 題目敘述
> *$n$ sprinklers are installed in a horizontal strip of grass $l$ meters long and $w$ meters wide.* <br><br>
> *Each sprinkler is installed at the horizontal center line of the strip.* <br><br>
> *For each sprinkler we are given its position as the distance from the left end of the center line and its radius of operation.*

### Question
> *What is the **minimim number** of sprinklers to turn on in order to **water the entire strip of grass?***


### Input format

> *Input consists of a number of cases.* <br><br>
> *The first line for each case contains integer numbers $n$, $l$ and $w$ with $n \leq 10000$.* <br><br>
> *The next $n$ lines contain two integers giving the position of a sprinkler and its radius of operation. (The picture above illustrates the first case from the sample input.)*

### Output format

> *For each test case output the **minimum** number of sprinklers needed to water the **entire** strip of grass. If it is **impossible** to water the entire strip output ‘-1’.*

### Sample Input

8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

### Sample Output

6
2
-1

---

## 概念
* 貪心
* 區間覆蓋

---

## 主要思路
* 首先，灑水器一律擺放至田地中央 $\frac{w}{2}$ 處，透過畢氏定理由 $\frac{w}{2}$ 與 $r$ 算出其可擴展到的左、右交點，如此便變成區間覆蓋問題


* 由二維題目轉變為單維，每個灑水器都有左、右可擴展到的交點位置，如上圖紅圈處標示，即代表在這區段之內的草坪皆可覆蓋到
* 接著依據左交點位置排序，而貪心在於每次查找時下一個必須涵蓋在當前的右交點內(其左交點必須在內)，並儘可能的往右覆蓋
* 當 $r < \frac{w}{2}$ 時，該灑水器要捨棄掉(沒辦法完全覆蓋草坪的灑水器)，此外若最左沒有覆蓋到0，或最右沒有覆蓋到 $l$，代表草坪無法覆蓋完全，則輸出 $-1$。

---

## 程式碼

#include <iostream>
#include <cmath>

using namespace std;

typedef struct S_pair
{
    double left;
    double right;
}s_pair;

//qsort compare function
int32_t compare(const void *a, const void *b)
{
    if ((((s_pair *)a)->left) > (((s_pair *)b)->left)) 
        return 1;
        
    return 0;
}

int main()
{

    int32_t n = 0, l = 0, w = 0;
    while (cin >> n >> l >> w)
    {
        s_pair arr[n];
        int32_t ans = 0;
        for (int32_t i = 0 ; i < n ; i ++)
        {
            int32_t pos = 0, r = 0;
            double len = 0;
            cin >> pos >> r;

            if (r < (double)(w/2))
            {
                //失效的灑水器往不可能的地方擺即可
                arr[i].left = l + 5000;
                arr[i].right= l + 5000;
            }
            else
            {
                len = sqrt(1.0 * r * r - (w/2.0)*(w/2.0));
                arr[i].left = pos - len;
                arr[i].right= pos + len;
            }

            //若當個灑水器可覆蓋全部則ans=1
            if (pos-len <= 0 && pos+len >= l) ans = 1;
        }

        if (ans) cout << "1" << endl;
        else
        {
            ans = 1;
           
            //依左交點排序 
            qsort(arr, n, sizeof(s_pair), compare);

            for (int32_t i = 0 ; i < n ; i++)
            {
                if (arr[i].right >= l) break;

                int32_t right_num = -1;

                for (int32_t j = i+1; j < n ; j++)
                {
                    int32_t temp = (arr[i].right >= arr[j].left);
                    if ((right_num == -1)&& temp ==1)
                    {
                        right_num = j;
                    }
                    else if (temp==1 && (arr[j].right > arr[right_num].right))
                        right_num = j;
                }

                i = right_num-1;
                ans +=1;
                if (right_num != -1 && arr[right_num].right >= l) break;

                //覆蓋失敗
                if (right_num == -1)
                {
                    ans = 0;
                    break;
                }
            }
            //覆蓋成功 
            if (ans!=0 && arr[0].left <= 0) cout << ans << endl;
            else cout << "-1" << endl;
        }
    }
    return 0;
}