Tắt đèn

Đ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

Bessie ở trong một chuồng bò hình đa giác đơn giản với $N$ đỉnh (liệt kê theo chiều kim đồng hồ). Cửa ra ở đỉnh $1$ . Các cạnh luôn song song với trục tọa độ (đa giác vuông góc).

Khi đèn tắt, Bessie ở tại một đỉnh nào đó (không biết đỉnh nào). Cô đi theo chiều kim đồng hồ dọc chu vi. Tại mỗi đỉnh, cô cảm nhận được góc trong (90° hoặc 270°), và độ dài cạnh cô vừa đi qua. Khi chuỗi quan sát chỉ khớp duy nhất một vị trí, cô biết mình ở đâu và chọn hướng ngắn nhất đến đỉnh $1$ .

Hãy tìm khoảng cách dư tối đa (so với khi biết vị trí từ đầu) trong trường hợp xấu nhất.

Dữ liệu vào

Dòng đầu: số nguyên $N$ .
$N$ dòng tiếp theo: tọa độ $(x_{i}, y_{i})$ của các đỉnh theo chiều kim đồng hồ.

Dữ liệu ra

Một số nguyên duy nhất — khoảng cách dư tối đa.

Ràng buộc

$4 \leq N \leq 200$
$- 100 000 \leq x_{i}, y_{i} \leq 100 000$

Ví dụ

Input	Output	Giải thích
4 0 0 0 10 1 10 1 0	2	Bắt đầu tại đỉnh 2: phải đi 12 đơn vị trong bóng tối (đi qua 1 cạnh mới biết vị trí, rồi quay lại), so với 10 đơn vị tối ưu. Dư 2.

Bình luận

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