QOJ.ac

QOJ

Limite de temps : 4.0 s Limite de mémoire : 512 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓

#11525. Rikka と湖

Statistiques

Peanut と LGD のおかげで、Rikka は S10 の期間中に大金を手に入れました。Rikka は、そのお金で土地を買い、屋敷を建てたいと考えています。

地図は 2 次元の直交座標系とみなせます。Rikka は点 $(0,0)$ に寝室を造ることにしました。地図上には単純多角形の形をした湖があります。もちろん、点 $(0,0)$ は湖の外にあります。

Rikka は走るのが大好きです。毎朝、寝室を出発し、まず距離 $k$ だけ走ってから、走って戻ってきます。そのため、どのような経路を選んでも、常に自分の敷地の中を走れるほど、敷地が広いことを望んでいます。Rikka は泳げないので、陸上だけを走ることに注意してください。

Rikka は無駄遣いをする女の子ではありません。敷地はできるだけ小さくしたいと考えています。そこで、敷地の面積としてありうる最小値を計算してください。

入力

最初の行には 2 つの整数 $n,k$ が与えられます($3\le n\le50$、$1\le k\le3000$)。それぞれ、湖の頂点数と Rikka が走れる距離を表します。

続く $n$ 行にはそれぞれ、2 つの整数 $x_i,y_i$ が与えられます($|x_i|,|y_i|\le200$)。これらは多角形の頂点の座標を表します。頂点は時計回りの順に与えられます。

点 $(0,0)$ が多角形の内部に厳密に含まれないことと、多角形の連続するどの 3 頂点も同一直線上にないことが保証されます。

出力

Rikka の敷地の面積としてありうる最小値を表す実数を 1 つ、1 行に出力してください。

答えの絶対誤差または相対誤差は $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

注記

1 つ目の例では、Rikka の敷地の最小面積は $\frac{7}{2}\pi$ です。可能な設計の 1 つを次の図に示します。

problem_11525_2af7e702aadcbcd74a6cf7bcbea89e72.png

2 つ目の例では、Rikka の敷地の最小面積は $\frac{29}{4}\pi+1$ です。可能な設計の 1 つを次の図に示します。

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