Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Äärettömällä pöydällä on annettu kaksi eri pistettä $A = (A_x, A_y)$ ja $B = (B_x, B_y)$.

Sinulla on myös $M$ tikkua, joista jokainen on pituudeltaan $W$ oleva jana. Voit asettaa nämä tikut mihin tahansa pöydälle, mihin tahansa paikkaan ja asentoon. Tikut saavat mennä päällekkäin. Mikään tikku ei kuitenkaan saa sisältää pistettä $A$ tai pistettä $B$.

Muurahainen lähtee pisteestä $A$ ja haluaa päästä pisteeseen $B$. Se voi kävellä missä tahansa pöydällä, paitsi että se ei voi ylittää yhtäkään tikkua.

Haluat asettaa tikut niin, että muurahaisen lyhimmän reitin pituus pisteestä $A$ pisteeseen $B$ on mahdollisimman suuri.

Jos muurahaisen kulku on mahdollista estää kokonaan niin, ettei reittiä pisteestä $A$ pisteeseen $B$ ole olemassa, vastaus on $-1$.

Muussa tapauksessa olkoon $L$ pisteestä $A$ pisteeseen $B$ kulkevien lyhimpien reittien pituuksien supremum$^\dagger$ kaikkien kelvollisten tikkujen asettelujen yli. Jos on olemassa asettelu, jolla tämä arvo saavutetaan, $L$ on yksinkertaisesti maksimi. Jos mikään yksittäinen asettelu ei saavuta sitä, mutta asetteluilla voidaan päästä mielivaltaisen lähelle sitä, sinun on silti tulostettava $L$.

$^\dagger$ Reaalilukujoukon supremum (pienin yläraja) on pienin reaaliluku, joka on suurempi tai yhtä suuri kuin jokainen joukon alkio. Joukon alkio voi saavuttaa sen tai sitten ei.

Syöte

Syöte annetaan seuraavassa muodossa:

T
A_x A_y B_x B_y M W
...
  • Kaikki syötearvot ovatkokonaislukuja.
  • $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$
  • On taattu, että $(A_x, A_y) \ne (B_x, B_y)$.

Tuloste

Jokaista testitapausta kohden:

  • Tulosta $-1$, jos muurahaisen kulku voidaan estää kokonaan;
  • Muussa tapauksessa tulosta yksi reaaliluku — yllä määritelty arvo $L$.

Olkoon $X$ oikea vastaus ja $Y$ tulosteesi. Tulosteesi katsotaan oikeaksi jos ja vain jos $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.

Esimerkki

Syöte 1

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

Tuloste 1

-1
1425074478.231629371643066

Huomautus

Testitapaus 1: Voidaan osoittaa, että asettelemalla tikut optimaalisesti muurahaisen kulku voidaan estää kokonaan.

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.