NYOJ ACM 12 喷水装置(2)

NYOJ ACM 12.





描述
有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。  


输入
第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。
输出
每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。
样例输入

2
2 8 6
1 1
4 5
2 10 6
4 5
6 5

样例输出

1
2



这个题跟第6题很类似,不过6是随便放置喷水龙头,只要按照半径大小排下来就行,这个题目龙头放置位置已经确定,稍微复杂一些.

思路:
根据每个龙头的x,r,还有草地的w和h,可以计算出(只计算半径比h/2大的龙头,否则不能用)喷水范围与草地边界的2个交点left和right,就将此题转化为一个线段覆盖问题.
用一个map<double,double>记录后,会自动按照left排序.如果第一个的left>0或者最大的right小于w,此题无解,直接输出0.结束.
否则开始外层死循环:
初始化龙头个数ind和rightmax,这个变量用来记录当前可以到达的最远的右端点.然后开始内层循环:内层循环的主要目的是,对于所有alive(可用的龙头,下面解释意义)的龙头,找到可以跟当前的rightmax接起来,并且能够右端最远的那个(因为要数目最小).循环中用一个curmax记录对于当前的rightmax可以到达的最远端.
循环中对于所有left小于rightmax的pair,如果其right不等于0(等于0意味着这个龙头不再alive,这个类似动态规划,来减少搜索的数目,考虑到小于rightmax的搜索过之后,新的rightmax不必再搜索上一次搜过的),并且right大于curmax,更新curmax,然后将当前pair的right置0,让它不再alive.内层循环结束后,如果curmax还是0,说明rightmax不能再增长,这是rightmax<w,输出0,不能覆盖.否则rightmax=curmax,更新rightmax,龙头数目加1后,继续下次外层循环.当外层循环结束,如果龙头个数ind不等于0,就输出ind.

#include <iostream>
#include <map>
#include <cmath>
#include <fstream>
using namespace std;

int main()
{
    ifstream cin("data.txt");
    int n,i;
    int m,w,h,x,r;
    double left, right;
    map <double,double> lar; // left and right
    map <double,double>::iterator it;
    double rightmax,curmax;
    int ind;
    cin >> n;
    while (n-->0)
    {
        lar.clear();
        rightmax = 0;
        cin >> m >> w >> h;
        for (i=0;i<m;i++)
        {
            cin >> x >> r;
            if (r<h/2.0) continue; // cannot be used, jump over
            left = x-sqrt(r*r-h*h/4.0); // left point
            right = x+sqrt(r*r-h*h/4.0); // right point
            lar[left] = right; // add to left-right list
            if (right>rightmax) rightmax = right;
        }
        it = lar.begin();
        if ((*it).first>0.0 || rightmax<w) // minimal bigger than 0 or maximal smaller than w
        {
            cout << 0 << endl;
            continue;
        }

        ind = 0; rightmax = 0.0;
        while (rightmax<(double)w)
        {
            curmax = 0.0;
            for (it=lar.begin();it!=lar.end();it++) // find the biggest right end with left<=rightmax
            {
                if ((*it).second==0.0) continue; // alive one
                if ((*it).first<=rightmax) // left<=rightmax
                {
                    if ((*it).second>curmax) // right>curmax
                    {
                        curmax = (*it).second; // mark the curmax right end
                    }
                    (*it).second = 0.0; // mark it has been checked
                }

            }
            if (curmax==0.0) // rightmax cannot be extended, mission failed
            {
                cout << 0 << endl;
                break;
            }
            else // update the rightmax, add count
            {
                rightmax = curmax;
                ind++;
                if (rightmax>=(double)w) break;
            }
        }
        if (ind>0) cout << ind << endl;
    }
}