QOJ.ac

QOJ

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

#11525. Rikka 與湖

الإحصائيات

多虧了 Peanut 與 LGD,Rikka 在 S10 期間賺了很多錢。Rikka 想用這筆錢買一塊地,並在上面興建莊園。

地圖可以視為一個二維笛卡兒座標系。Rikka 決定把臥室建在點 $(0,0)$。地圖上有一座湖,其形狀是一個簡單多邊形。當然,點 $(0,0)$ 位於湖外。

Rikka 喜歡跑步。每天早上,Rikka 都會從臥室出發,先跑出 $k$ 單位的距離,再跑回來。因此,Rikka 希望莊園夠大,使她無論如何規劃路線,都始終在莊園內跑步。請注意,由於 Rikka 不會游泳,她只會在陸地上跑步。

Rikka 不是個浪費的女孩,她希望莊園越小越好。因此,她想請你計算莊園可能的最小面積。

輸入格式

第一行包含兩個整數 $n,k$($3 \le n \le 50$,$1 \le k \le 3000$),表示湖的頂點數,以及 Rikka 能跑出的距離。

接下來有 $n$ 行,每行包含兩個整數 $x_i,y_i$($|x_i|,|y_i| \le 200$),表示多邊形頂點的座標。這些頂點按順時針順序給出。

輸入保證點 $(0,0)$ 不嚴格位於多邊形內部,且多邊形中任意三個連續頂點不共線。

輸出格式

輸出一行,包含一個實數,表示 Rikka 莊園可能的最小面積。

你的答案的絕對誤差或相對誤差應小於 $10^{-6}$。

範例

輸入格式 1

4 2
0 0
0 1
1 1
1 0

輸出格式 1

10.995574287564

輸入格式 2

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

輸出格式 2

23.776546738526

說明

第一個範例中,Rikka 莊園可能的最小面積為 $\frac{7}{2}\pi$。下圖展示了一種可行的方案。

problem_11525_48c84419184bf5235fb83cf9ffbca2b9.png

第二個範例中,Rikka 莊園可能的最小面積為 $\frac{29}{4}\pi+1$。下圖展示了一種可行的方案。

problem_11525_ea68d70ccfe4a73768162aadf9da6470.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.