QOJ.ac

QOJ

Límite de tiempo: 4.0 s Límite de memoria: 512 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓

#11525. Rikka 同湖

Estadísticas

多得 Peanut 同 LGD,Rikka 喺 S10 期間贏咗好多錢。Rikka 想用呢筆錢買一塊地,喺上面起一個莊園。

地圖可以視為二維笛卡兒座標系。Rikka 決定喺點 $(0,0)$ 起佢嘅睡房。地圖上有一個湖,形狀係簡單多邊形。當然,點 $(0,0)$ 喺湖外。

Rikka 鍾意跑步。每日朝早,佢會由睡房出發,先跑出去 $k$ 單位距離,再跑返嚟。所以 Rikka 希望莊園夠大,無論佢點樣規劃路線,都一直喺自己嘅莊園入面。留意,由於 Rikka 唔識游水,佢只會喺陸地上跑。

Rikka 唔係浪費嘅女仔:佢想莊園盡可能細。所以佢想你計算莊園最細可能嘅面積。

輸入

第一行包含兩個整數 $n,k$($3\le n\le50$,$1\le k\le3000$),分別表示湖嘅頂點數目同 Rikka 可以跑嘅距離。

接落嚟有 $n$ 行。每行包含兩個整數 $x_i,y_i$($|x_i|,|y_i|\le200$),表示多邊形頂點嘅座標。頂點按順時針次序畀出。

輸入保證點 $(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 莊園最細可能嘅面積係 $\frac72\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.