oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

journey Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

journey.html

While Ben and Gwen got to the last piece of the Map of Infinity before Aggregor did, Ben did not safeguard the map piece well and sacrificed it to save the Sentinel. Hence, Aggregor has got the final map piece and is travelling to the Forge of Creation to absorb the power of a baby Celestialsapien in order to be the most powerful alien in the whole universe!

Ben and Gwen realizes that they have to travel to the Forge of Creation and try to put up one last battle with Aggregor to stop him from having ultimate power. However, the Forge of Creation is only accessible via a series of beacons which are placed around it.

Each beacon has an effective radius and if you travel within its effective radius, you will enjoy a speed bonus. Each beacon has the ability to direct you to the next beacon of your choice. While you are moving from one beacon to another, you will enjoy the speed bonus until you reach the outside of the effective radius of the beacon. From then on, you cannot receive any speed bonus from any other beacon except the one that you have selected as your next endpoint.

You will begin your journey to the Forge of Creation by travelling to a beacon from your current location. Similarly, you will end your journey by travelling from a beacon to the Forge of Creation. During your entire journey, you may only travel in straight lines. When you are travelling normally, your speed is 3 distance units / second, whereas when sped up by the beacons, you travel at the speed of sound, 340 distance units / second.

During your journey, you may only travel in straight lines, turning only when you are at the centre of a beacon.

The first line of input will consist of an integer representing the number of beacons, n (0 < n ≤ 500).

The next line of input will consist of two integers representing your current co-ordinates.

The next line of input will consist of two integers representing the co-ordinates of the Forge of Creation.

The next n lines of input will consist of three integers, the first two integers of the line represent the co-ordinates of the beacon and the third integer represents the effective radius.

All coordinates will be no less than -10000 and no more than 10000. The radius of each beacon will be between 1 and 100, inclusive.

Given this information, find the shortest time possible to reach the Forge of Creation, accurate to 1 decimal place.

Sample Input

3
0 0
10 6
2 2 2
6 2 2
9 5 1

Sample Output

0.9

Tags

Graph Theory, NOI 2011 Sec Selection Test 1

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o journey -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.