[USACO08OPEN]牛的街区Cow Neighborhoods

题目描述

Those Who Know About Cows are aware of the way cows group into 'Cow Neighborhoods'. They have observed Farmer John's N (1 <= N <= 100,000) cows (conveniently numbered 1..N) as they graze, each at her own unique integer rectilinear coordinate, on a pasture whose X and Y coordinates are in the range 1..1,000,000,000. Two cows are neighbors if at least one of two criteria is met: 1) If the cows are no further than some integer Manhattan distance C (1 <= C <= 1,000,000,000) apart, they are neighbors. [Manhattan distance is calculated as d = |x1-x2| + |y1-y2|.] 2) If cow A is a neighbor of cow Z and cow B is a neighbor of cow Z, then cow A is a neighbor of cow B (the 'transitive closure of neighbors'). Given the locations of the cows and the distance C, determine the the number of neighborhoods and the number of cows in the largest neighborhood. By way of example, consider the pasture below. When C = 4, this pasture has four neighborhoods: a big one on the left, two neighborhoods of size 1 (the lonesome cows), and a huge neighborhood on the right with 60 different cows. ```cpp .....................................*................. ....*...*..*.......................***................. ......*...........................****................. ..*....*..*.......................*...*.******.*.*..... ........................*.............***...***...*.... *..*..*...*..........................*..*...*..*...*... .....................................*..*...*..*....... .....................................*..*...*..*....... ...*................*.................................. .*..*............................*.*.*.*.*.*.*.*.*.*.*. .*.....*..........................*.*.*.*.*.*.*.*.*.*.* ....*.................................................. ``` The input file describes cow locations by integer X,Y coordinates, where the lower left corner is (1,1) and cows close to that corner appear at both (2,2) and (5,1) in the example above. For a given pasture, determine both the number of cow neighborhoods and the number of cows resident in the largest cow neighborhood. The above picture is sample test case 2, which will be evaluated for you upon submission. Partial feedback for some test cases will be provided on the first 10 submissions. Time Limit: 2 seconds Memory Limit: 32MB 了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标$X_i,Y_i(1\leq X_i,Y_i\leq [1 \cdots 10^9]$;$X_i,Y_i \in \text{整数}$.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的: 1.两只奶牛的曼哈顿距离不超过$C(1\leq C\leq 10^9)$,即$|X_i - x_i|+|Y_i - y_i|\leq C$. 2.两只奶牛有共同的邻居.即,存在一只奶牛$k$,使$i$与$k$,$j$与$k$均同属一个群. 给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

输入输出格式

输入格式


\* Line 1: Two space-separated integers: N and C \* Lines 2..N+1: Line i+1 describes cow i's location with two space-separated integers: X\_i and Y\_i

输出格式


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

输入输出样例

输入样例 #1

4 2 
1 1 
3 3 
2 2 
10 10 

输出样例 #1

2 3 

说明

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.