trang chủ / đề bài / icpcwf17_a

Xây dựng sân bay

Đề bài

Mô tả

Quốc đảo nhiệt đới Piconesia nổi tiếng với những bãi biển tuyệt đẹp, thảm thực vật tươi tốt, các đồn điền ca cao và cà phê, cùng thời tiết tuyệt vời quanh năm. Thiên đường này đang được cân nhắc làm địa điểm tổ chức một kỳ ICPC World Finals trong tương lai (hoặc ít nhất là nơi nghỉ dưỡng cho ban điều hành). Chỉ có một vấn đề nhỏ: hòn đảo thật sự rất khó đến.

Hiện tại, cách nhanh nhất để tới đảo mất ba ngày tính từ sân bay gần nhất, dùng kết hợp thuyền đánh cá, tàu chở dầu, thuyền kayak và tàu ngầm. Để việc tham dự ICPC World Finals dễ dàng hơn một chút và để thúc đẩy ngành du lịch của đảo, Piconesia dự định xây sân bay đầu tiên của mình.

Vì đường băng càng dài thì càng đón được máy bay lớn, Piconesia quyết định xây đường băng dài nhất có thể trên đảo. Đáng tiếc là họ chưa xác định được nên đặt đường băng ở đâu. Có lẽ bạn giúp được họ?

Trong bài này, đường bờ biển của Piconesia được mô hình hóa bằng một đa giác. Cho đa giác này, hãy tính độ dài của đường băng (tức một đoạn thẳng) dài nhất có thể xây trên đảo. Đường băng không được cắt vào biển, nhưng có thể chạm hoặc chạy dọc theo đường biên của đảo.

Hình dưới ứng với ví dụ thứ nhất.

Hình: hòn đảo được mô hình hóa bằng một đa giác. Đường băng dài nhất có thể xây được vẽ bằng nét đậm.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n, số đỉnh của đa giác. Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên x và y: tọa độ (x,y) của các đỉnh đa giác theo thứ tự ngược chiều kim đồng hồ.

Đa giác là đa giác đơn: các đỉnh đôi một phân biệt, và không có hai cạnh nào của đa giác cắt nhau hoặc chạm nhau, ngoại trừ hai cạnh liên tiếp chạm nhau tại đỉnh chung. Ngoài ra, không có hai cạnh liên tiếp nào thẳng hàng.

Dữ liệu ra

In ra độ dài của đoạn thẳng dài nhất nằm trọn trong đa giác. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−6.

Ràng buộc

  • 3≤n≤200.
  • |x|,|y|≤106.

Ví dụ

Input Output Giải thích
7
0 20
40 0
40 20
70 50
50 70
30 50
0 50
76.157731059 Đây là hòn đảo trong hình: đường băng dài nhất nối đỉnh (0,20) với đỉnh (70,50), dài 702+302≈76,1577.
3
0 2017
-2017 -2017
2017 0
4510.149110617 Đảo là một tam giác; đoạn dài nhất là một cạnh, chẳng hạn cạnh nối (0,2017) với (−2017,−2017), dài 20175.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0