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 và độ rộng của máy quét là : phần được quét là một dải thẳng đứng , trong đó 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 và : 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 dòng tiếp theo chứa hai số nguyên và : 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á .
Ràng buộc
- .
- Mọi tọa độ là số nguyên có giá trị tuyệt đối không vượt quá .
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 . Dải tốt nhất là , phần tam giác nằm trong dải có diện tích . |
| 3 40 60 10 50 50 0 0 |
1111.1111111111113 | Tam giác có diện tích . Dải tốt nhất là , diện tích quét được là . Mọi kết quả sai lệch không quá đều được chấp nhận. |
Bình luận