TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1923
  • 题目
  • P1923【平衡树】奶牛的邻居
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    一些了解奶牛的人来到了FJ的农场观察FJ的N (1 <= N <=100,000)头奶牛,为了方便编号为1..N。每头牛在牧场里都有他单独的坐标X、Y(1<=X , Y <=1,000,000,000)。

    两头牛如果满足了以下两个条件之一便是邻居:
    1.如果他们的曼哈顿距离小于C (1 <= C <= 1,000,000,000)。曼哈顿距离是|x1-x2| + |y1-y2|。
    2.如果Z是A的邻居,同时Z也是B的邻居,那么A就是B的邻居。

    给出奶牛的坐标和C,求出有多少的奶牛群和最大的奶牛群有多少只奶牛(奶牛群中的奶牛都是邻居关系)。
    例如,当C=4时有如下地图,共4个奶牛群,最右边的奶牛群最大,有60头牛


    ......................................................
    ....
    .............................................
    ......
    ............................................
    ..
    ....
    .............................
    .......
    ........................
    .......................
    ..............................................
    ...................................................
    ...................................................
    .....................................................
    ..........................................
    .
    .........................................
    ....*..................................................

    输入格式

    第一行,两个整数N和C
    接下来N行,每行两个整数,表示一头牛的坐标

    输出格式

    两个整数,表示奶牛群的数量和最大奶牛群包含的奶牛数

    样例输入

    4 2 
    1 1 
    3 3 
    2 2 
    10 10
     

    样例输出

    2 3


    来源  Usaco Open08 Gold Cow Neighborhoods