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ồ. 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 chính xác góc trong tại đỉnh đó 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ó. Bessie quyết định dùng chiến lược sau: cô sẽ di chuyển theo chiều kim đồng hồ quanh chu vi chuồng cho đến khi cảm nhận đủ góc và cạnh để suy ra mình hiện đang ở đỉnh nào. 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, bằng cách tiếp tục đi theo chiều kim đồng hồ hoặc đổi hướng và đi ngược chiều kim đồng hồ.

Hãy giúp Bessie xác định mức tăng lớn nhất 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.

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 lớn nhất của quãng đường Bessie phải đi tại vị trí xuất phát xấu nhất khi dùng chiến lược được mô tả trong đề bài.

Ví dụ

4
0 0
0 10
1 10
1 0

2

Nguồn

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

Tác giả: Brian Dean.