Farmer John lắp máy vắt sữa mới hiện đại trong chuồng, nhưng nó tiêu thụ quá nhiều điện nên đôi khi gây mất điện! Chuyện xảy ra thường xuyên đến mức Bessie đã thuộc bản đồ chuồng để dễ tìm lối ra trong tối. Tuy nhiên, cô muốn biết mất điện ảnh hưởng đến việc ra nhanh thế nào, chẳng hạn phải đi xa thêm bao nhiêu trong tối.

Chuồng là đa giác đơn (không tự cắt), có các đỉnh nguyên $(x_1, y_1) \ldots (x_n, y_n)$ theo chiều kim đồng hồ. Cạnh luân phiên ngang (song song trục $x$) và dọc (trục $y$); cạnh đầu có thể là loại nào cũng được. Lối ra ở $(x_1, y_1)$. Bessie bắt đầu trong chuồng tại một đỉnh $(x_i, y_i)$ với $i > 1$. Cô chỉ được đi trên chu vi, theo hoặc ngược chiều kim đồng hồ, và muốn khoảng cách nhỏ nhất tới lối ra. Có đèn thì dễ: chọn chiều ngắn hơn từ vị trí hiện tại đến lối ra.

Một ngày đèn tắt khiến Bessie hoảng và quên đỉnh mình đang đứng. Cô vẫn nhớ bản đồ chính xác nên có thể suy ra vị trí bằng cách đi và sờ. Ở mỗi đỉnh, kể cả đỉnh đầu, cô cảm nhận góc trong chính xác và biết đó có phải lối ra không. Sau khi đi hết một cạnh, cô biết độ dài chính xác của cạnh. Cô dùng chiến lược đi theo chiều kim đồng hồ đến khi cảm nhận đủ góc và cạnh để suy ra đỉnh hiện tại. Sau đó cô đi quãng đường còn lại nhỏ nhất đến lối ra, tiếp tục cùng chiều hoặc đổi sang ngược chiều kim đồng hồ.

Hãy tìm mức tăng khoảng cách lớn nhất trong tối so với chuồng sáng, trong trường hợp xấu nhất trên tất cả đỉnh bắt đầu có thể.

Dữ liệu vào

Dòng đầu chứa $N$ ($4 \leq N \leq 200$). Mỗi dòng trong $N$ dòng tiếp theo có hai số nguyên mô tả $(x_i, y_i)$ theo chiều kim đồng hồ. Các số thuộc $-100,000 \ldots 100,000$.

Dữ liệu ra

In mức tăng khoảng cách lớn nhất ở vị trí đầu xấu nhất khi dùng chiến lược đã mô tả.

Ví dụ

Dữ liệu vào 1

4
0 0
0 10
1 10
1 0

Dữ liệu ra 1

2

Ghi chú

Trong ví dụ, Bessie cảm nhận góc đầu là 90 độ nhưng không phân biệt được đỉnh 2, 3 hay 4. Sau khi đi một cạnh theo chiều kim đồng hồ, cô đến lối ra hoặc xác định duy nhất vị trí nhờ độ dài cạnh. Khoảng cách là:

Từ đỉnh 2: đi 12 đơn vị trong tối (1 đến đỉnh 3 rồi 11 đến lối ra), nhưng chỉ 10 khi có đèn. Khoảng cách thêm là 2.

Từ đỉnh 3: 11 đơn vị trong cả hai trường hợp.

Từ đỉnh 4: 1 đơn vị trong cả hai trường hợp.

Do đó chênh lệch xấu nhất là $12 - 10 = 2$. Chiến lược bảo đảm, dù bắt đầu ở đâu, cô chỉ đi thêm tối đa 2 đơn vị trong tối so với có đèn.

Tác giả bài toán: Brian Dean