Vùng hàng xóm bò

View as PDF

Submit solution

Points: 1.60 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
USACO US-Open 2008 - Bảng Vàng
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Những người-biết-về-bò đã nhận ra cách mà các con bò nhóm lại thành các "vùng hàng xóm bò". Họ đã quan sát ~N~ ~(1 \le N \le 100~, ~000)~ con bò của nông dân John (để tiện ta sẽ đánh số các con bò từ ~1~ ...~N)~ khi chúng đi ăn cỏ, tọa độ của các con bò là khác nhau và là các số nguyên, coi đồng cỏ là hình chữ nhật có các tọa độ ~X~ và ~Y~ trong khoảng ~1~ ...~1~, ~000~, ~000~, ~000~.

Hai con bò là hàng xóm nếu có ~1~ trong ~2~ điều kiện sau:

  1. Khoảng cách Manhattan của các con bò không lớn hơn ~1~ số nguyên ~C~ cho trước ~(1 \le C \le 1~, ~000~, ~000~, ~000)~. [Khoảng cách Manhattan tính như sau: ~d =|x_1-x_2| +|y_1-y_2|~.]
  2. Nếu bò ~A~ là hàng xóm của bò ~Z~ và bò ~B~ cũng là hàng xóm của bò ~Z~ thì bò ~A~ và bò ~B~ cũng là hàng xóm.

Một vùng hàng xóm bò là một tập các con bò là hàng xóm của nhau và không là hàng xóm của bất kỳ con bò nào khác ngoài tập này. Cho vị trí của các con bò và khoảng cách ~C~, xác định số vùng hàng xóm bò và vùng có nhiều bò nhất.

Ví dụ như ở hình bên dưới là đồng cỏ. Với ~C = 4~, đồng cỏ này có ~4~ vùng hàng xóm bò: ~1~ vùng lớn ở bên trái, ~2~ vùng nhỏ có kích thước ~1~ (các con bò cô đơn), và một vùng rất lớn ở bên phải với ~60~ con bò.

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

Dữ liệu từ tập tin input sẽ mô tả các tọa độ bằng các số nguyên ~X~, ~Y~ với vị trí góc trái dưới là ~(1~, ~1)~ và các con bò ở gần góc này nằm ở vị trí ~(2~, ~2)~ và ~(5~, ~1)~ trong ví dụ ở trên.

Input

  • Dòng ~1~: ~2~ số nguyên cách nhau bởi dấu cách: ~N~ và ~C~
  • Dòng ~2~ ...~N + 1~: Dòng ~i + 1~ mô tả vị trí của con bò thứ ~i~ gồm ~2~ số nguyên cách nhau bởi dấu cách: ~X_i~ và ~Y_i~

Output

  • Dòng ~1~: ~2~ số nguyên cách nhau bởi dấu cách tương ứng là số vùng hàng xóm bò và số lượng bò ở vùng lớn nhất.

Sample Input

4 2
1 1
3 3
2 2
10 10

Sample Output

2 3

Note

Có ~2~ vùng bò, một vùng là ~3~ con bò đầu tiên và vùng thứ ~2~ là các con bò còn lại. Vùng lớn nhất có ~3~ con bò.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.