Farmer John đã lắp một chiếc máy vắt sữa hiện đại mới trong chuồng, nhưng nó tiêu thụ nhiều điện đến mức thỉnh thoảng làm mất điện! Việc này xảy ra thường xuyên đến nỗi Bessie đã ghi nhớ bản đồ chuồng, giúp cô dễ tìm lối ra hơn trong bóng tối. Tuy nhiên, cô tò mò về ảnh hưởng của việc mất điện đến khả năng nhanh chóng thoát khỏi chuồng. Chẳng hạn, cô muốn biết mình có thể phải đi xa hơn bao nhiêu để tìm được lối ra trong bóng tối.

Chuồng được mô tả bởi một đa giác đơn (không tự cắt) có các đỉnh nguyên \((x_1,y_1)\ldots(x_n,y_n)\) được liệt kê theo chiều kim đồng hồ. Các cạnh luân phiên nằm ngang (song song với trục \(x\)) và thẳng đứng (song song với trục \(y\)); cạnh đầu tiên có thể thuộc một trong hai loại. Lối ra nằm tại \((x_1,y_1)\). Bessie bắt đầu ở bên trong chuồng tại một đỉnh nào đó \((x_i,y_i)\) với \(i>1\). Cô chỉ có thể đi quanh chu vi chuồng theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ và có thể đổi hướng mỗi khi đến một đỉnh. Mục tiêu của cô là đi quãng đường ngắn nhất để đến lối ra. Khi đèn sáng, điều này tất nhiên khá dễ: từ vị trí hiện tại, cô sẽ đi đến lối ra theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, tùy hướng nào ngắn hơn.

Một ngày nọ, đèn tắt khiến Bessie hoảng sợ và quên mất mình đang đứng ở đỉnh nào. May thay, cô vẫn nhớ chính xác bản đồ chuồng, nên có thể xác định vị trí bằng cách đi quanh chuồng và dùng xúc giác. Mỗi khi đứng tại một đỉnh (kể cả đỉnh ban đầu), cô có thể cảm nhận đó là một chỗ rẽ trái hay rẽ phải và biết được đỉnh ấy có phải lối ra hay không. Khi đi dọc một cạnh của chuồng, sau khi đi hết cạnh đó cô có thể xác định chính xác độ dài của nó. Nói chung, Bessie sẽ dùng một chiến lược để dò đường quanh đỉnh xuất phát cho đến khi có đủ thông tin để xác định mình đang ở đâu. Khi đó, cô có thể dễ dàng tìm đường đến lối ra với quãng đường còn lại nhỏ nhất.

Hãy giúp Bessie xác định mức tăng nhỏ nhất có thể của quãng đường cô phải đi trong trường hợp xấu nhất (xét mọi đỉnh xuất phát có thể) khi đi trong bóng tối so với khi chuồng được chiếu sáng, với giả định cô di chuyển theo một chiến lược tối ưu trong mỗi trường hợp. Một chiến lược "tối ưu" cho trường hợp không có ánh sáng là chiến lược làm nhỏ nhất mức tăng trong trường hợp xấu nhất này.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(4\le N\le200\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên mô tả các điểm \((x_i,y_i)\) theo thứ tự chiều kim đồng hồ quanh chuồng. Các số nguyên này nằm trong khoảng \(-100\,000\ldots100\,000\).

Dữ liệu ra

In mức tăng nhỏ nhất có thể trong trường hợp xấu nhất mà theo đó quãng đường tối ưu của Bessie trong bóng tối dài hơn quãng đường tối ưu của cô trong chuồng sáng, trong đó trường hợp xấu nhất được xét trên mọi đỉnh mà Bessie có thể xuất phát.

Ví dụ

4
0 0
0 10
1 10
1 0

2

Nguồn

USACO 2016 January Contest, Platinum - Lights Out: https://usaco.org/index.php?page=viewproblem2&cpid=602

Tác giả: Brian Dean.