trang chủ / đề bài / icpc22_mb_c

Máy bán hàng tự động

Đề bài

Mô tả

Trường đại học cuối cùng đã quyết định lắp đặt những chiếc máy bán hàng tự động được ưa chuộng ở nhiều vị trí chiến lược trong khuôn viên. Thực ra, để bù đắp cho tình trạng thiếu máy trước đây, trường quyết định lắp càng nhiều máy càng tốt.

Đáng ngạc nhiên là khuôn viên sẽ không bị lấp kín bởi máy mới, vì có những quy định pháp lý khá nghiêm ngặt về vị trí đặt máy. Trường đã đánh dấu mọi vị trí có thể đặt máy bán hàng cùng tọa độ của chúng trên bản đồ khuôn viên. Ngoài ra, trường còn phải tuân thủ quy tắc an toàn của nhà sản xuất: khoảng cách giữa hai máy bán hàng bất kỳ phải ít nhất là 1,3 mét. Hãy giúp trường xác định số máy bán hàng lớn nhất có thể lắp đặt trong khuôn viên.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa số nguyên N là số vị trí có thể đặt máy trên bản đồ (1≤N≤2000). Tiếp theo là N dòng mô tả tọa độ các vị trí, mỗi dòng mô tả một vị trí bằng một cặp tọa độ nguyên, tính bằng mét. Các vị trí trong cùng một bộ dữ liệu đôi một khác nhau. Mọi tọa độ đều không âm và không vượt quá 109.

Đảm bảo rằng mọi vị trí tạo thành một nhóm liên thông duy nhất, tức là có thể bắt đầu từ một vị trí bất kỳ và đi tới mọi vị trí khác bằng một dãy bước, mỗi bước thay đổi đúng một tọa độ đi 1, mà không rời khỏi khu vực được phép đặt máy.

Dữ liệu vào kết thúc ở cuối tệp.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên là số máy bán hàng lớn nhất có thể lắp đặt trong khuôn viên.

Ràng buộc

  • 1≤N≤2000.
  • 0≤ mọi tọa độ ≤109, các vị trí trong một bộ dữ liệu đôi một khác nhau.
  • Các vị trí của một bộ dữ liệu liên thông theo các bước thay đổi một tọa độ đi 1.

Ví dụ

Input Output Giải thích
4
0 0
0 1
1 0
1 1
6
0 1
1 0
1 1
1 2
1 3
2 2
2
4
Bộ thứ nhất là hình vuông 2×2: chọn hai góc chéo nhau (0,0) và (1,1), cách nhau 2≈1,41 mét. Bộ thứ hai chọn được (0,1), (1,0), (1,3) và (2,2).
1
5 5
3
0 0
1 0
2 0
5
0 0
0 1
1 1
2 1
2 0
1
2
3
Bộ thứ hai chọn (0,0) và (2,0). Bộ thứ ba chọn (0,0), (1,1) và (2,0).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0