#BZOJ1604. Cow Neighborhoods 奶牛的邻居
-
ID: 3840
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Cow Neighborhoods 奶牛的邻居
No submission language available for this problem.
题目描述
了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的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行输入N和C，之后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.