trang chủ / đề bài / icpc21_mn_n

Từ sao Hỏa tới sao Thổ

Đề bài

Mô tả

Sau khi đọc bài báo nghiên cứu về công việc và giấc ngủ, lập trình viên sao Hỏa "điên rồ" Phidang muốn đi thám hiểm và tìm kiếm sự sống trên một hành tinh mới: sao Thổ. Vì vậy, anh dự định phóng một tàu vũ trụ từ sao Hỏa tới sao Thổ. Tàu vũ trụ của anh mang một máy quét khổng lồ để quét bề mặt sao Thổ.

Giả sử bề mặt sao Thổ là một đa giác trên mặt phẳng, và tàu vũ trụ bay phía trên nó. Máy quét trên tàu chiếu tia laser xuống bề mặt. Cụ thể, tàu bay theo một đường thẳng song song với trục Oy và độ rộng của máy quét là L: phần được quét là một dải thẳng đứng x0≤x≤x0+L, trong đó x0 là số thực tùy chọn. Diện tích được thám hiểm là diện tích phần đa giác nằm trong dải này.

Anh Phidang muốn diện tích được thám hiểm là lớn nhất. Hãy giúp anh tìm diện tích lớn nhất đó.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và L: số đỉnh của đa giác mô tả bề mặt sao Thổ và độ rộng của máy quét.
  • Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên xi và yi: tọa độ các đỉnh của đa giác.

Các đỉnh được cho theo chiều ngược chiều kim đồng hồ. Đa giác không tự cắt và không tự tiếp xúc.

Dữ liệu ra

In ra diện tích lớn nhất có thể quét được. Sai số tuyệt đối hoặc tương đối không vượt quá 10−4.

Ràng buộc

  • 1≤n,L≤20000.
  • Mọi tọa độ là số nguyên có giá trị tuyệt đối không vượt quá 104.

Ví dụ

Input Output Giải thích
3 3
0 0
5 1
1 7
14.28 Tam giác có diện tích 17. Dải tốt nhất là 0.4≤x≤3.4, phần tam giác nằm trong dải có diện tích 14.28.
3 40
60 10
50 50
0 0
1111.1111111111113 Tam giác có diện tích 1250. Dải tốt nhất là 503≤x≤1703, diện tích quét được là 100009. Mọi kết quả sai lệch không quá 10−4 đều được chấp nhận.

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