QOJ.ac

QOJ

Süre Sınırı: 4.0 s Bellek Sınırı: 512 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓

#11525. Rikka dan Danau

İstatistikler

Berkat Peanut dan LGD, Rikka memenangkan banyak uang selama S10. Rikka ingin menggunakan uang itu untuk membeli sebidang tanah dan membangun sebuah kediaman beserta lahannya.

Peta dapat dianggap sebagai sistem koordinat Kartesius dua dimensi. Rikka memutuskan membangun kamar tidurnya pada titik $(0, 0)$. Terdapat sebuah danau di peta yang berbentuk poligon sederhana. Tentu saja, titik $(0, 0)$ berada di luar danau.

Rikka suka berlari. Setiap pagi, dimulai dari kamar tidurnya, Rikka mula-mula akan berlari sejauh $k$ satuan jarak, lalu berlari kembali. Oleh karena itu, Rikka ingin lahannya cukup luas sehingga bagaimana pun ia merencanakan lintasannya, ia selalu berlari di dalam lahannya. Perhatikan bahwa Rikka hanya akan berlari di daratan karena ia tidak dapat berenang.

Rikka bukan gadis yang boros: ia ingin lahannya sekecil mungkin. Karena itu, ia ingin Anda menghitung luas minimum yang mungkin untuk lahannya.

Masukan

Baris pertama berisi dua bilangan bulat $n$, $k$ ($3 \le n \le 50$, $1 \le k \le 3000$), yang menyatakan banyaknya titik sudut danau dan jarak yang dapat ditempuh Rikka dengan berlari.

Kemudian diikuti $n$ baris. Setiap baris berisi dua bilangan bulat $x_i$, $y_i$ ($|x_i|, |y_i| \le 200$), yang menyatakan koordinat titik-titik sudut poligon. Titik-titik sudut diberikan dalam urutan searah jarum jam.

Masukan menjamin bahwa titik $(0, 0)$ tidak berada secara ketat di dalam poligon, dan tidak ada tiga titik sudut berurutan yang segaris.

Keluaran

Keluarkan satu baris berisi satu bilangan real, yaitu luas minimum yang mungkin untuk lahan Rikka.

Jawaban Anda harus memiliki galat absolut atau relatif kurang dari $10^{-6}$.

Contoh

Masukan 1

4 2
0 0
0 1
1 1
1 0

Keluaran 1

10.995574287564

Masukan 2

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

Keluaran 2

23.776546738526

Catatan

Untuk contoh pertama, luas minimum yang mungkin untuk lahan Rikka adalah $\frac{7}{2}\pi$. Salah satu rancangan yang mungkin ditampilkan pada gambar berikut.

problem_11525_2af7e702aadcbcd74a6cf7bcbea89e72.png

Untuk contoh kedua, luas minimum yang mungkin untuk lahan Rikka adalah $\frac{29}{4}\pi + 1$. Salah satu rancangan yang mungkin ditampilkan pada gambar berikut.

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.