Best Route in ChefLand
All submissions for this problem are available.
ChefLand is a strange place. In the middle of deepest ocean, Code-sea, there are two small islands P and Q. Also there is one big circular country, known as C in the middle of the ocean. This country do not allow anyone inside their airspace ever. However, there is roadways in the perimeter of the (circular) country. Anyone is allowed in the road at any time. A lot of airports are available in that circular road. One can take a flight from any point from the road. Similarly you can land at any point in the road. A lot of airports !
Little Ira is currently in island P . She has to go to island Q. The traveling cost per unit distance in the air is CA. Traveling cost per unit distance in the road is CR. A plane can fly anywhere except in the restricted zone, i.e., inside the circular airspace.
Ira wants to go to city Q using minimum cost. She can either travel directly from P to Q using a single flight (of course without violating the restricted zone). Or, she can fly from P to the circular roadway, then may be travel some distance using roadways and then again take a flight from the road to Q. She just wants to minimize the total traveling cost. Help her.
- The whole ocean can be modeled as 2-D Cartesian plane. Where the center of the circular road and Origin coincide.
- Islands P and Q can be assigned x and y co-ordinates, say Px and Py etc.
- Let the radius of the circle be R.
- Distance here is defined as euclidean distance.
- Cost will be distance multiplied by corresponding rate (CR or CA).
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The only line of each test case contains five integers - Px, Py, Qx, Qy and R, and two real numbers - CA and CR. All space separated in that order.
- The real numbers will contain exactly three digits after decimal. There will be no leading zeros. Example - zero will be represented as 0.000 and not 00.000 etc.
- P and Q lies strictly outside the circle C
- For each test case, output a single line containing the minimum cost in which her tour can be completed.
- Your output will be considered correct if it is within the error of 0.01 with the jury's output.
- 1 ≤ T ≤ 100
- -104 ≤ Px, Py, Qx, Qy ≤ 104
- 0 ≤ Ca, Cr ≤ 103
- 1 ≤ R ≤ 104
Input: 3 -4 0 4 1 2 100.000 0.002 -2 0 2 0 1 100.000 0.001 -2 0 -2 -10 1 100.000 0.001 Output: 412.322149 200.003142 1000.000000
Example case 1. See the image above for illustration.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.