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 haluaa mennä ”Cloud End Ruins” -raunioiden Eye of Dawnin keskustaan etsimään aarteita, mutta hänen tiellään on $n$ muuria. $i$:s muuri on ympyrä, jonka keskipiste on origossa $(0, 0)$ ja säde on $r_i$. Muurissa on $k_i$ ovea, ja $j$:nnen oven koordinaatit ovat $\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)$. Muurin paksuus ja ovien leveys ovat mitättömän pieniä, eikä Hyacinthia voi lentää muurien yli.

Hyacinthia haluaa kysyä sinulta $m$ kertaa. Joka kerta hän kertoo sinulle lähtöpisteensä, ja sinun tulee vastata, mikä on lyhin etäisyys keskustaan. Lähtöpisteen taataan olevan muurin sisäpuolella ja aivan muurin pinnan vieressä.

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n, m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$), jotka kuvaavat muurien lukumäärää ja kyselyiden lukumäärää.

Seuraavat $n$ riviä kuvaavat kunkin muurin. Jokainen rivi alkaa kahdella kokonaisluvulla $r_i, k_i$ ($1 \le r_i \le 10^8, 0 \le k_i \le 2 \cdot 10^5$), jotka kertovat, että $i$:s muuri on ympyrä, jonka säde on $r_i$ ja jossa on $k_i$ ovea. Tämän jälkeen rivillä on $k_i$ kokonaislukua $p_{i,1}, p_{i,2}, \dots, p_{i,k_i}$, jotka kertovat, että $j$:nnen oven koordinaatit ovat $\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)$, missä $M = 3.6 \cdot 10^8$. Taataan, että $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$ ja $1 \le r_1 < r_2 < \dots < r_n \le 10^8$.

Seuraavat $m$ riviä sisältävät kukin kaksi kokonaislukua $t_i, q_i$, jotka kysyvät, mikä on lyhin etäisyys origoon, jos Hyacinthia lähtee $t_i$:nnen muurin sisäpuolelta pisteestä $\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)$ (jos origoon ei pääse, tulosta "-1").

Tuloste

Tulosta jokaiseen kyselyyn omalle rivilleen liukuluku, joka kuvaa vastausta. Jos perille ei pääse, tulosta "-1". Vastaus katsotaan oikeaksi, jos suhteellinen tai absoluuttinen virhe mallivastaukseen verrattuna on enintään $10^{-6}$.

Esimerkit

Syöte 1

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

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