QOJ.ac

QOJ

実行時間制限: 4.0 s メモリ制限: 512 MB 満点: 100 難易度: [表示] ハック可能 ✓

#11525. Rikka y el lago

統計

Gracias a Peanut y LGD, Rikka ganó mucho dinero durante S10. Rikka quiere utilizar ese dinero para comprar un terreno y construir en él una mansión con su finca.

El mapa puede considerarse un sistema de coordenadas cartesianas bidimensional. Rikka decide construir su dormitorio en el punto $(0, 0)$. Hay un lago en el mapa cuya forma es un polígono simple. Por supuesto, el punto $(0, 0)$ está fuera del lago.

A Rikka le encanta correr. Cada mañana, saliendo de su dormitorio, primero correrá alejándose una distancia de $k$ unidades y después regresará. Por tanto, Rikka desea que su finca sea lo suficientemente grande para que, sea cual sea el recorrido que planee, siempre corra dentro de ella. Ten en cuenta que Rikka solo correrá por tierra, ya que no sabe nadar.

Rikka no es una chica derrochadora: quiere que su finca sea lo más pequeña posible. Por tanto, quiere que calcules el área mínima posible de su finca.

Entrada

La primera línea contiene dos enteros $n, k$ ($3 \le n \le 50$, $1 \le k \le 3000$), que representan el número de vértices del lago y la distancia que Rikka puede correr.

A continuación hay $n$ líneas. Cada línea contiene dos enteros $x_i, y_i$ ($|x_i|, |y_i| \le 200$), que representan las coordenadas de los vértices del polígono. Estos vértices se dan en sentido horario.

Se garantiza que el punto $(0, 0)$ no está estrictamente dentro del polígono y que no hay tres vértices consecutivos del polígono en una misma recta.

Salida

Imprime una sola línea con un único número real: el área mínima posible de la finca de Rikka.

Tu respuesta debe tener un error absoluto o relativo inferior a $10^{-6}$.

Ejemplos

Entrada 1

4 2
0 0
0 1
1 1
1 0

Salida 1

10.995574287564

Entrada 2

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

Salida 2

23.776546738526

Nota

Para el primer ejemplo, el área mínima posible de la finca de Rikka es $\frac{7}{2}\pi$. En la siguiente figura se muestra una posible disposición.

problem_11525_48c84419184bf5235fb83cf9ffbca2b9.png

Para el segundo ejemplo, el área mínima posible de la finca de Rikka es $\frac{29}{4}\pi + 1$. En la siguiente figura se muestra una posible disposición.

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.