Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Little Ika: Doo Doo Doo $\sim$.

Hyacinthia ønsker å dra til sentrum av «Cloud End Ruins» Eye of Dawn for å lete etter skatter, men det er $n$ murer som blokkerer veien hennes. Den $i$-te muren er en sirkel med sentrum i origo $(0, 0)$ og radius $r_i$. Det er $k_i$ dører i muren, og koordinatene til den $j$-te døren er gitt ved $\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)$. Tykkelsen på muren og bredden på dørene er neglisjerbare, og Hyacinthia kan ikke fly over murene.

Hyacinthia vil spørre deg $m$ ganger. Hver gang forteller hun deg startpunktet sitt, og du må svare hva den korteste avstanden til sentrum er. Startpunktet er garantert å være på innsiden av en mur og helt inntil muroverflaten.

Inndata

Den første linjen inneholder to heltall $n, m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$), som representerer antall murer og antall spørringer.

De neste $n$ linjene beskriver hver mur. Hver linje starter med to heltall $r_i, k_i$ ($1 \le r_i \le 10^8, 0 \le k_i \le 2 \cdot 10^5$), som betyr at den $i$-te muren er en sirkel med radius $r_i$ og har $k_i$ dører. Deretter følger $k_i$ heltall $p_{i,1}, p_{i,2}, \dots, p_{i,k_i}$, som betyr at koordinatene til den $j$-te døren er $\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)$, der $M = 3.6 \cdot 10^8$. Det er garantert at $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$ og $1 \le r_1 < r_2 < \dots < r_n \le 10^8$.

De neste $m$ linjene inneholder hver to heltall $t_i, q_i$, som angir at hvis Hyacinthia starter fra innsiden av den $t_i$-te muren i punktet $\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)$, hva er den korteste avstanden til origo (hvis det ikke er mulig å nå frem, skriv ut "-1").

Utdata

For hver spørring skal du skrive ut én enkelt linje med et flyttall som representerer svaret. Hvis det ikke er mulig å nå frem, skriv ut "-1". Et svar regnes som riktig hvis den relative eller absolutte feilen ikke overstiger $10^{-6}$ sammenlignet med fasitsvaret.

Eksempler

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