Universal Cup Judging System

Universal Cup

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

小伊卡(Little Ika):嘟嘟嘟 $\sim$。

風堇(Hyacinthia)想要去「雲端遺蹟」黎明之眼(Eye of Dawn)嘅中心搵戰利品,但係有 $n$ 道牆擋住咗佢嘅去路。第 $i$ 道牆係一個以原點 $(0, 0)$ 為圓心、半徑為 $r_i$ 嘅圓。牆上面有 $k_i$ 道門,第 $j$ 道門嘅座標由 $\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)$ 畀出。牆嘅厚度同埋門嘅闊度都可以忽略不計,而且風堇唔可以飛越牆壁。

風堇想問你 $m$ 次。每次佢都會話畀你知佢嘅起點,你需要回答去到中心嘅最短距離係幾多。保證起點位於某道牆嘅內側,而且貼住牆面。

輸入格式

第一行包含兩個整數 $n, m$($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$),分別表示牆嘅數量同埋詢問次數。

跟住落嚟嘅 $n$ 行描述每道牆。每行開頭有兩個整數 $r_i, k_i$($1 \le r_i \le 10^8, 0 \le k_i \le 2 \cdot 10^5$),表示第 $i$ 道牆係一個半徑為 $r_i$ 而且有 $k_i$ 道門嘅圓。隨後係 $k_i$ 個整數 $p_{i,1}, p_{i,2}, \dots, p_{i,k_i}$,表示第 $j$ 道門嘅座標為 $\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)$,其中 $M = 3.6 \cdot 10^8$。保證 $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$,而且 $1 \le r_1 < r_2 < \dots < r_n \le 10^8$。

跟住落嚟嘅 $m$ 行,每行包含兩個整數 $t_i, q_i$,表示如果風堇由第 $t_i$ 道牆內側嘅點 $\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)$ 出發,去到原點嘅最短距離係幾多(如果去唔到,請輸出 "-1")。

輸出格式

對於每次詢問,輸出一行一個浮點數表示答案。如果去唔到,輸出 "-1"。同標準答案相比,如果相對誤差或者絕對誤差唔超過 $10^{-6}$,就視為答案正確。

範例

輸入格式 1

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

輸出格式 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.