QOJ.ac

QOJ

حد الوقت: 4.0 s حد الذاكرة: 512 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓

#11525. Rikka và hồ nước

الإحصائيات

Nhờ Peanut và LGD, Rikka đã thắng được rất nhiều tiền trong S10. Rikka muốn dùng số tiền này để mua một mảnh đất và xây một trang viên trên đó.

Bản đồ có thể được coi là một hệ tọa độ Descartes hai chiều. Rikka quyết định xây phòng ngủ của mình tại điểm $(0, 0)$. Trên bản đồ có một hồ nước có hình dạng là một đa giác đơn. Tất nhiên, điểm $(0, 0)$ nằm ngoài hồ.

Rikka thích chạy bộ. Mỗi buổi sáng, xuất phát từ phòng ngủ, đầu tiên Rikka sẽ chạy đi một quãng đường $k$ đơn vị rồi chạy trở về. Vì vậy, Rikka mong trang viên của mình đủ rộng để dù cô lên kế hoạch cho đường chạy như thế nào, cô cũng luôn chạy trong trang viên. Lưu ý rằng Rikka chỉ chạy trên đất liền vì cô không biết bơi.

Rikka không phải là một cô gái hoang phí: cô muốn trang viên của mình nhỏ nhất có thể. Vì vậy, cô muốn bạn tính diện tích nhỏ nhất có thể của trang viên.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$, $k$ ($3 \le n \le 50$, $1 \le k \le 3000$), biểu thị số đỉnh của hồ và quãng đường Rikka có thể chạy.

Tiếp theo là $n$ dòng. Mỗi dòng chứa hai số nguyên $x_i$, $y_i$ ($|x_i|, |y_i| \le 200$), biểu thị tọa độ của các đỉnh đa giác. Các đỉnh này được cho theo thứ tự chiều kim đồng hồ.

Dữ liệu vào bảo đảm rằng điểm $(0, 0)$ không nằm hẳn bên trong đa giác, và không có ba đỉnh liên tiếp nào của đa giác nằm trên cùng một đường thẳng.

Dữ liệu ra

In ra một dòng chứa một số thực duy nhất, là diện tích nhỏ nhất có thể của trang viên Rikka.

Đáp án của bạn phải có sai số tuyệt đối hoặc tương đối nhỏ hơn $10^{-6}$.

Ví dụ

Dữ liệu vào 1

4 2
0 0
0 1
1 1
1 0

Dữ liệu ra 1

10.995574287564

Dữ liệu vào 2

6 3
1 0
1 1
0 1
0 2
2 2
2 0

Dữ liệu ra 2

23.776546738526

Ghi chú

Trong ví dụ thứ nhất, diện tích nhỏ nhất có thể của trang viên Rikka là $\frac{7}{2}\pi$. Một phương án có thể được minh họa trong hình sau.

problem_11525_66719a22e2db05aa124033f2d9fd8a52.png

Trong ví dụ thứ hai, diện tích nhỏ nhất có thể của trang viên Rikka là $\frac{29}{4}\pi + 1$. Một phương án có thể được minh họa trong hình sau.

problem_11525_142930a5db8a56e970e5c4573e1c461a.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#2635EditorialOpen$\Theta(n)$ 题解 by ChatGPT AnonymousView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.