Chu vi (Bạc)

Đ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 $10^{6} \times 10^{6}$ . 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 50000$
$1 \leq x_{i}, y_{i} \leq 10^{6}$
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 10005 200003 10005 200004 10008 200004 10005 200005 10006 200003 10007 200003 10007 200004 10006 200005	14	Cùng hình dạng với bản Bronze, tọa độ lớn hơn.

Bình luận

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