Submeter | Todas submissőes | Melhores | Voltar |
NABOR - 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:
- 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|.]
- 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.
.....................................*................. ....*...*..*.......................***................. ......*...........................****................. ..*....*..*.......................*...*.******.*.*..... ........................*.............***...***...*.... *..*..*...*..........................*..*...*..*...*... .....................................*..*...*..*....... .....................................*..*...*..*....... ...*................*.................................. .*..*............................*.*.*.*.*.*.*.*.*.*.*. .*.....*..........................*.*.*.*.*.*.*.*.*.*.* ....*..................................................
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.
Input
- 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
Output
- Line 1: A single line with a two space-separated integers: the number of cow neighborhoods and the size of the largest cow neighborhood.
Example
Input: 4 2 1 1 3 3 2 2 10 10 Output: 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.
Adicionado por: | Wanderley Guimarăes |
Data: | 2008-06-06 |
Tempo limite: | 0.100s |
Tamanho do fonte: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Linguagem permitida: | ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Origem: | USACO Open 2008 - Gold |