QOJ.ac

QOJ

Time Limit: 4.0 s Memory Limit: 512 MB Total points: 100 Difficulty: [show] Hackable ✓

#11525. 六花与湖

Statistics

多亏了 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

说明 1

对于第一个样例,Rikka 庄园的最小面积为 $\frac{7}{2}\pi$。一种可能的方案如下图所示。

样例输入 2

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

样例输出 2

23.776546738526

说明 2

对于第二个样例,Rikka 庄园的最小面积为 $\frac{29}{4}\pi + 1$。一种可能的方案如下图所示。

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.