Tắt đèn

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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 đang ở trong một cái chuồng có hình dạng đa giác đơn (không tự giao) với $N$ đỉnh nguyên $(x_{1}, y_{1}), \dots, (x_{N}, y_{N})$ theo thứ tự chiều kim đồng hồ. Các cạnh của chuồng xen kẽ nhau giữa nằm ngang và thẳng đứng (cạnh đầu tiên có thể thuộc loại bất kỳ). Lối ra nằm tại đỉnh $(x_{1}, y_{1})$ .

Khi đèn bật, Bessie biết mình đang đứng ở đỉnh nào và có thể đi đến lối ra bằng cách chọn hướng ngắn hơn (theo kim đồng hồ hoặc ngược chiều kim đồng hồ) dọc theo chu vi chuồng.

Khi đèn tắt, Bessie quên mất mình đang ở đỉnh nào. Tuy nhiên, Bessie vẫn nhớ bản đồ chuồng và có thể dùng cảm giác để định hướng:

Tại mỗi đỉnh cô đến (kể cả đỉnh ban đầu), cô cảm nhận được đây là góc ngoặt trái hay phải, và có thể nhận biết lối ra.
Khi đi dọc một cạnh, cô biết chính xác độ dài cạnh đó sau khi đi xong.

Bessie sẽ di chuyển chiến lược để tìm hiểu vị trí của mình (bằng cách ghi nhớ chuỗi các góc ngoặt và độ dài cạnh đã thấy), sau đó đi đến lối ra theo khoảng cách ngắn nhất.

Hãy tính khoảng cách dư thừa tệ nhất (worst-case extra distance) tối thiểu mà Bessie phải đi trong tối so với khi đèn sáng, giả sử Bessie dùng chiến lược tối ưu trong cả hai trường hợp. Kết quả lấy worst-case trên tất cả các đỉnh xuất phát có thể.

Dữ liệu vào

Dòng đầu: số nguyên $N$ ( $4 \leq N \leq 200$ ).
$N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x_{i}, y_{i}$ ( $- 100000 \leq x_{i}, y_{i} \leq 100000$ ) là tọa độ đỉnh thứ $i$ theo thứ tự chiều kim đồng hồ.

Dữ liệu ra

In ra một số nguyên duy nhất: khoảng cách dư thừa worst-case tối thiểu khi đi trong tối so với khi có đèn.

Ràng buộc

$4 \leq N \leq 200$
Các tọa độ trong khoảng $[- 100000, 100000]$
Đa giác đơn giản (không tự giao), các cạnh xen kẽ nằm ngang và thẳng đứng

Ví dụ

Input	Output	Giải thích
4 0 0 0 10 1 10 1 0	2	Bessie cảm nhận tất cả các góc đều quặt vào trong, nên ban đầu cô không xác định được vị trí. Một chiến lược tối ưu là luôn đi theo chiều kim đồng hồ. Nếu xuất phát từ đỉnh 3 hoặc 4, đây là tối ưu; nếu xuất phát từ đỉnh 2, cô phải đi thêm 2 đơn vị.
8 0 0 0 10 4 10 4 5 6 5 6 10 10 10 10 0	10	Đa giác 8 đỉnh hình chữ U ngược (chuồng có chỗ lõm vào trong). Lối ra tại (0,0). Trong trường hợp xấu nhất, Bessie phải đi thêm 10 đơn vị.

Ghi chú

Đỉnh $(x_{1}, y_{1})$ là lối ra (đỉnh đặc biệt mà Bessie có thể nhận ra khi chạm vào).
Bessie chỉ được di chuyển dọc theo chu vi, và có thể đổi hướng tại bất kỳ đỉnh nào.
"Khoảng cách dư thừa" = (khoảng cách đi trong tối) - (khoảng cách tối ưu khi biết vị trí).

Bình luận

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