Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Little Ika: Doo Doo Doo $\sim$.

Hyacinthia vill ta sig till mitten av "Cloud End Ruins" Eye of Dawn för att leta efter byte, men det finns $n$ murar som blockerar hennes väg. Den $i$-te muren är en cirkel med centrum i origo $(0, 0)$ och radie $r_i$. Det finns $k_i$ dörrar på muren, och koordinaterna för den $j$-te dörren ges av $\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)$. Murens tjocklek och dörrarnas bredd är försumbara, och Hyacinthia kan inte flyga över murarna.

Hyacinthia vill fråga dig $m$ gånger. Varje gång berättar hon sin startpunkt, och du ska svara vad det kortaste avståndet till mitten är. Startpunkten garanteras ligga på insidan av en mur och precis intill murytan.

Indata

Den första raden innehåller två heltal $n, m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$), som representerar antalet murar och antalet frågor.

De följande $n$ raderna beskriver varje mur. Varje rad börjar med två heltal $r_i, k_i$ ($1 \le r_i \le 10^8, 0 \le k_i \le 2 \cdot 10^5$), som anger att den $i$-te muren är en cirkel med radie $r_i$ och har $k_i$ dörrar. Därefter följer $k_i$ heltal $p_{i,1}, p_{i,2}, \dots, p_{i,k_i}$, som anger att koordinaterna för den $j$-te dörren är $\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)$, där $M = 3.6 \cdot 10^8$. Det garanteras att $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$ samt $1 \le r_1 < r_2 < \dots < r_n \le 10^8$.

De följande $m$ raderna innehåller var och en två heltal $t_i, q_i$, som anger att om Hyacinthia startar från insidan av den $t_i$-te muren i punkten $\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)$, vad är det kortaste avståndet till origo (om det inte går att nå, skriv ut "-1").

Utdata

För varje fråga, skriv ut en ensam rad med ett flyttal som representerar svaret. Om det inte går att nå, skriv ut "-1". Ett svar betraktas som korrekt om det relativa eller absoluta felet inte överstiger $10^{-6}$ jämfört med standardsiffran.

Exempel

Indata 1

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

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