TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3662
  • 题目
  • P3662划区灌溉
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    约翰的奶牛们发现山脊上的草特别美味.为了维持草的生长,约翰打算安装若干喷灌器.为简化问题,山脊可以看成一维的数轴,长为L(1≤L≤10^6),而且L-定是一个偶数.每个喷灌器可以双向喷灌,并有确定的射程,该射程不短于A,不长于B,A,B(1≤A≤B≤10^3)都是给出的正整数.它所在位置的两边射程内,都属它的灌溉区域.注意,一个喷灌器往左右两边喷射的距离是一样的,比如往左喷的距离是x,那么往右也是x,(A<=x<=B)。
    现要求山脊的每一个区域都被灌溉到,喷灌器不能将水喷到山脊以外的区域,而且喷灌器的灌溉区域不允许重叠, 约翰有N(1≤N≤10^3)只奶牛,每一只都有特别喜爱的草区,第i奶牛喜爱的草区是[Si,Ei],不同奶牛的草区可以重叠(Ei-Si<=2*B).现要求,每只奶牛的草区仅被一个喷灌器灌溉. 寻找最少需要的喷灌器数目.

    输入格式

    第一行,两个整数N和L
    第二行,两个整数A和B
    接下来N行,每行两个整数S和E(0 <= S < E <= L),表示每头奶牛喜欢的草区的起止位置

    输出格式

    一行,一个整数,表示最少需要的喷灌器的数量,若无解,输出-1

    样例输入

    样例输入1:
    2 8
    1 2
    6 7
    3 6

    样例输入2:
    4 202
    10 12
    21 27
    32 39
    103 121
    163 180

    样例输出

    样例输出1:
    3

    样例输出2:
    10

    提示

    样例1说明:


    来源  usaco 2004 dec gold