Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Little Ika: Doo Doo Doo $\sim$.

Hyacinthia ingin pergi ke pusat "Cloud End Ruins" Eye of Dawn untuk mencari harta rampasan, tetapi terdapat $n$ dinding yang menghalangi jalannya. Dinding ke-$i$ adalah sebuah lingkaran yang berpusat di titik asal $(0, 0)$ dengan jari-jari $r_i$. Terdapat $k_i$ pintu pada dinding tersebut, dan koordinat dari pintu ke-$j$ diberikan oleh $\left(r_i \cdot \cos\left(\frac{2\pi}{M} \cdot p_{i,j}\right), r_i \cdot \sin\left(\frac{2\pi}{M} \cdot p_{i,j}\right)\right)$. Ketebalan dinding dan lebar pintu dapat diabaikan, serta Hyacinthia tidak dapat terbang melewati dinding.

Hyacinthia ingin bertanya kepada Anda sebanyak $m$ kali. Setiap kali ia akan memberi tahu titik awalnya, dan Anda perlu menjawab berapa jarak terpendek menuju pusat. Titik awal dijamin berada di sisi dalam suatu dinding dan tepat menempel pada permukaan dinding.

Masukan

Baris pertama berisi dua bilangan bulat $n, m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$), yang menyatakan banyaknya dinding dan banyaknya pertanyaan.

$n$ baris berikutnya mendeskripsikan setiap dinding. Setiap baris diawali dengan dua bilangan bulat $r_i, k_i$ ($1 \le r_i \le 10^8, 0 \le k_i \le 2 \cdot 10^5$), yang menyatakan bahwa dinding ke-$i$ adalah lingkaran berjari-jari $r_i$ dan memiliki $k_i$ pintu. Selanjutnya diikuti oleh $k_i$ bilangan bulat $p_{i,1}, p_{i,2}, \dots, p_{i,k_i}$, yang menyatakan bahwa koordinat pintu ke-$j$ adalah $\left(r_i \cdot \cos\left(\frac{2\pi}{M} \cdot p_{i,j}\right), r_i \cdot \sin\left(\frac{2\pi}{M} \cdot p_{i,j}\right)\right)$, dengan $M = 3.6 \cdot 10^8$. Dijamin bahwa $0 \le p_{i,1} < p_{i,2} < \dots < p_{i,k_i} < M$, $k_n = 0$, $\sum_{i=1}^n k_i \le 2 \cdot 10^5$, dan $1 \le r_1 < r_2 < \dots < r_n \le 10^8$.

$m$ baris berikutnya masing-masing berisi dua bilangan bulat $t_i, q_i$, yang menyatakan bahwa jika Hyacinthia mulai dari sisi dalam dinding ke-$t_i$ pada titik $\left(r_{t_i} \cdot \cos\left(\frac{2\pi}{M} \cdot q_i\right), r_{t_i} \cdot \sin\left(\frac{2\pi}{M} \cdot q_i\right)\right)$, berapakah jarak terpendek menuju titik asal (jika tidak dapat dicapai, silakan keluarkan "-1").

Keluaran

Untuk setiap pertanyaan, keluarkan satu baris berisi bilangan titik-mengambang (floating-point) yang menyatakan jawabannya. Jika tidak dapat dicapai, keluarkan "-1". Jawaban dianggap benar jika galat relatif atau absolutnya tidak melebihi $10^{-6}$ dibandingkan dengan jawaban standar.

Contoh

Masukan 1

3 4
2 2 0 90000000
5 0
8 0
1 114514
2 0
2 180000000
3 233

Keluaran 1

2.0000000000
5.0000000000
7.4056093871
-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.