Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Little Ika: Doo Doo Doo $\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)$ ความหนาของกำแพงและความกว้างของประตูถือว่าน้อยมากจนไม่ต้องนำมาคิด และ Hyacinthia ไม่สามารถบินข้ามกำแพงได้

Hyacinthia ต้องการถามคุณ $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$ ซึ่งหมายความว่าหาก Hyacinthia เริ่มต้นจากด้านในของกำแพงชั้นที่ $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.