5604: BZOJ1604:[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l≤Xi,Yi≤[1..10^9];Xi,Yi∈整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:   1.两只奶牛的曼哈顿距离不超过C(1≤C≤10^9),即lXi - xil+IYi - Yil≤C.   2.两只奶牛有共同的邻居.即,存在一只奶牛k,使i与k,j与k均同属一个群.     给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛


输入格式

   1行输入NC,之后N行每行输入一只奶牛的坐标.


输出格式

仅一行,先输出牛群数,再输出最大牛群里的牛数,用空格隔开.


样例输入

4 2
1 1
3 3
2 2
10 10

* Line 1: A single line with a two space-separated integers: the
        number of cow neighborhoods and the size of the largest cow
        neighborhood.




样例输出

2 3

OUTPUT DETAILS:
There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.


提示

没有写明提示


题目来源

Gold

加入题单

上一题 下一题 算法标签: