Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

על שולחן אינסופי נתונות שתי נקודות שונות $A = (A_x, A_y)$ ו-$B = (B_x, B_y)$.

יש לך גם $M$ מקלות, שכל אחד מהם הוא קטע ישר באורך $W$. באפשרותך להניח את המקלות הללו בכל מקום על השולחן, בכל מיקום ובכל כיוון. המקלות רשאים לחפוף. עם זאת, אף מקל אינו יכול להכיל את הנקודה $A$ או את הנקודה $B$.

נמלה מתחילה ב-$A$ ורוצה להגיע אל $B$. היא יכולה ללכת בכל מקום על השולחן, פרט לכך שאינה יכולה לחצות אף מקל.

ברצונך להניח את המקלות כך שאורך המסלול הקצר ביותר עבור הנמלה מ-$A$ אל $B$ יהיה גדול ככל האפשר.

אם ניתן לחסום את הנמלה לחלוטין כך שלא קיים מסלול מ-$A$ אל $B$, התשובה היא $-1$.

אחרת, יהי $L$ הסופרמום$^\dagger$ של אורכי המסלולים הקצרים ביותר מ-$A$ אל $B$ על פני כל ההנחות החוקיות של המקלות. אם קיימת הנחה שמשיגה ערך זה, $L$ הוא פשוט המקסימום. אם אף הנחה בודדת אינה משיגה אותו, אך הנחות יכולות להתקרב אליו כרצוננו, עדיין עליך להדפיס את $L$.

$^\dagger$ הסופרמום (החסם העליון הקטן ביותר) של קבוצת מספרים ממשיים הוא המספר הממשי הקטן ביותר שגדול או שווה לכל ערך בקבוצה. הוא עשוי להתקבל או שלא להתקבל על ידי ערך בקבוצה.

קלט

הקלט ניתן בפורמט הבא:

T
A_x A_y B_x B_y M W
...
  • כל ערכי הקלט הם מספרים שלמים.
  • $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_x, A_y) \ne (B_x, B_y)$.

פלט

עבור כל מקרה בדיקה:

  • הדפס $-1$ אם ניתן לחסום את הנמלה לחלוטין;
  • אחרת, הדפס מספר ממשי יחיד — הערך $L$ שהוגדר לעיל.

יהי $X$ התשובה הנכונה ו-$Y$ הפלט שלך. הפלט שלך ייחשב לנכון אם ורק אם $|Y - X| \le 10^-6 \cdot \max(1, |X|)$.

דוגמה

קלט 1

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

פלט 1

-1
1425074478.231629371643066

הערה

מקרה בדיקה 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.