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

Á óendanlegu borði eru gefnir tveir ólíkir punktar $A = (A_x, A_y)$ og $B = (B_x, B_y)$.

Þú ert líka með $M$ prik, þar sem hvert prik er strik af lengd $W$. Þú mátt setja þessi prik hvar sem er á borðið, í hvaða stöðu og stefnu sem er. Prikin mega skarast. Hins vegar má ekkert prik innihalda punktinn $A$ eða punktinn $B$.

Maur byrjar í $A$ og vill komast í $B$. Hann má ganga hvar sem er á borðinu, nema hvað hann getur ekki farið yfir neitt prik.

Þú vilt raða prikunum þannig að lengd stystu leiðar maursins frá $A$ til $B$ verði eins mikil og mögulegt er.

Ef hægt er að loka alveg fyrir maurinn þannig að engin leið sé til frá $A$ til $B$, þá er svarið $-1$.

Annars látum við $L$ vera efra mark (supremum)$^\dagger$ lengda stystu leiða frá $A$ til $B$ yfir allar gildar uppsetningar á prikunum. Ef til er uppsetning sem nær þessu gildi, þá er $L$ einfaldlega hámarkið. Ef engin einstök uppsetning nær því, en uppsetningar geta komist eins nálægt því og vera vill, verður þú samt að prenta $L$.

$^\dagger$ Efra mark (minnsta יfirmark) mengis rauntalna er minnsta rauntalan sem er stærri en eða jöfn hverju gildi í menginu. Það getur annaðhvort náðst af gildi í menginu eða ekki.

Inntak

Inntakið er gefið á eftirfarandi sniði:

T
A_x A_y B_x B_y M W
...
  • Öll inntaksgildi eru heiltölur.
  • $1 \le T \le 10^4$
  • $0 \le A_x, A_y, B_x, B_y \le 10^9$
  • $1 \le M, W \le 10^9$
  • Það er tryggt að $(A_x, A_y) \ne (B_x, B_y)$.

Úttak

Fyrir hvert prófunartilvik:

  • Prentaðu $-1$ ef hægt er að loka alveg fyrir maurinn;
  • Annars skaltu prenta eina rauntölu — gildið $L$ sem skilgreint er hér að ofan.

Látum $X$ vera rétta svarið og $Y$ vera úttakið þitt. Úttakið þitt telst rétt ef og aðeins ef $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.

Dæmi

Inntak 1

2
0 0 1 1 343 434
4 5 786331192 707731892 1 639711202

Úttak 1

-1
1425074478.231629371643066

Athugasemd

Prófunartilvik 1: Hægt er að sýna fram á að með því að raða prikunum á besta hátt má loka alveg fyrir maurinn.

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.