trang chủ / bài tập / perimb

Chu vi (Đồng)

Đề bài

Mô tả

Có N kiện cỏ khô được đặt trên một lưới 100×100. Mỗi kiện chiếm một ô lưới và tất cả các kiện tạo thành một vùng liên thông (có thể đi từ ô này sang ô khác qua 4 hướng bắc/nam/đông/tây). Vùng có thể có lỗ hổng bên trong (các ô trống bị bao quanh hoàn toàn bởi các kiện cỏ). Lỗ hổng không đóng góp vào chu vi.

Hãy tính chu vi của vùng hình thành bởi các kiện cỏ (không tính chu vi của lỗ hổng).

Dữ liệu vào

  • Dòng 1: Số nguyên N
  • Dòng i+1 (với 1≤i≤N): Hai số nguyên xi và yi — tọa độ của kiện cỏ thứ i

Dữ liệu ra

  • Một số nguyên duy nhất: chu vi của vùng

Ràng buộc

  • 1≤N≤10000
  • 1≤xi,yi≤100
  • Tất cả các kiện cỏ tạo thành một vùng liên thông
  • Không có hai kiện cỏ trùng vị trí

Ví dụ

Input Output Giải thích
8
5 3
5 4
8 4
5 5
6 3
7 3
7 4
6 5		 14 Vùng có hình chữ C/U biến thể với chu vi ngoài là 14.
40
48 47
50 51
50 53
49 48
49 54
50 54
49 47
52 51
54 51
53 52
51 50
49 49
47 50
47 48
51 51
48 50
53 51
46 48
45 50
49 52
50 49
48 46
50 48
50 52
46 49
50 50
46 52
46 50
47 47
48 48
47 49
52 50
51 52
47 51
45 51
49 51
48 49
46 51
49 50
45 49		 46 Vùng gồm 40 kiện cỏ xếp thành hình dạng phức tạp có chu vi 46.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0