Hotline : +84 0988.131.808       endefr
  1. Xuân Bắc
  2. Thảo luận Internet CNTT
  3. Thứ năm, Tháng 3 16 2017, 02:38 PM
  4.  Đăng ký qua email

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 <= N <= 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 <= C <= 1,000,000,000). [Khoảng cách Manhattan tính như sau: d = |x1-x2| + |y1-y2|.]
  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.

Hình trên là test ví dụ số 2, test này sẽ dùng để đánh giá bài nộp của bạn.

Một phần kết quả của một số test ví dụ sẽ được thông báo ở 10 lần nộp đầu tiên.

Dữ liệu

  • 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
Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
Bích Liên Chấp nhận Trả lời
0
Bầu chọn

Kết quả

  • 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.

Ví dụ

Dữ liệu
4 2
1 1
3 3
2 2
10 10

Kết quả
2 3

Giải thích

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ò.

Bình luận
Không có ý kiến đóng góp nào.
Thêm bình luận
  1. hơn một tháng trước đây
  2. Thảo luận Internet CNTT
  3. Trả lời này
  • Trang :
  • 1


Không có trả lời ở đây.
khách
Gửi phản hồi của bạn
Tải lên tập tin hoặc hình ảnh cho cuộc thảo luận này bằng cách nhấp vào nút tải ở dưới. hỗ trợ gif,jpg,png,zip,rar
• Xóa s (Maximum File Size: 2 MB)
Bạn có thể chèn các thăm dò ý kiến vào bài viết của bạn. Các cuộc thăm dò sau đó sẽ xuất hiện trong bài viết.
Tùy chọn bỏ phiếu
Chia sẻ vị trí

Chia sẻ vị trí hiện tại của bạn trong khi đăng một câu hỏi mới cho phép người xem để xác định vị trí bạn đang nằm.

Vi độ:
Kinh độ:
  • Bùi Văn Lương
    1897.00 Điểm
  • Hoàng Tiến An
    1502.00 Điểm
  • Phạm Minh Anh
    1335.00 Điểm
  • Hoàng Trung Kiên
    1197.00 Điểm
  • Nguyễn Anh Đông
    1165.00 Điểm
  • Nguyễn Văn Cường
    1042.00 Điểm
  • Hoàng Mạnh Thái
    942.00 Điểm
  • Hoàng Anh Thư
    815.00 Điểm
  • Hoàng Thế Anh
    792.00 Điểm
  • Triệu Hùng Cường
    692.00 Điểm
  • Hoàng Thị Mai
    625.00 Điểm
  • Triệu Mai Anh
    237.00 Điểm
  • Lưu Phương Dung
    162.00 Điểm
  • Phạm Thị Hồng
    142.00 Điểm
  • Hoàng Thế Quỳnh
    87.00 Điểm