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) олжа іздеу үшін «Бұлт шетіндегі қирандылар» Таң Көзінің (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$ есігі бар екенін білдіреді. Одан кейін $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)$ екенін білдіретін $k_i$ бүтін сан $p_{i,1}, p_{i,2}, \dots, p_{i,k_i}$ беріледі, мұндағы $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.