Chu vi (Đồng)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ kiện cỏ khô được đặt trên một lưới $100 \times 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 \leq i \leq N$ ): Hai số nguyên $x_{i}$ và $y_{i}$ — 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 \leq N \leq 10000$
$1 \leq x_{i}, y_{i} \leq 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.