Problem Description
Package delivery is really a tiring work. I’m spending all day on the roads, crossing bridges and highways through the city, and visiting various people in different buildings. Anytime someone asks me if I’m busy, stressed or overworked and the answer will likely be an emphatic yes.
But I have my experience in my job. At the beginning of the day, I arrive at the company and receive the packages of today’s work. Before I set out to deliver them, I have to carefully consider which package should be sent first and which way I should go. It’s really a heavy headache for me.
The city consists of totally M two-way roads, each of which is a straight segment line or a circle. A straight one contains two endpoints that can be denoted as Ai(xiA,yiA) and Bi(xiB,yiB) on a two-dimensional map, while a circle-shaped road should be expressed as a centre point Oi(xi,yi) and its radius Ri. Roads may cross with others (even on the endpoint), but no two roads will overlap. The coordinates and radius are measured in centimetre (cm) and the scale of the map is 1: 100000. That is, two locations with actual distance of 1 kilometre (km) will be 1cm apart on the map. Further more, roads are not neccessarily connected in the city.
My company locates at (Cx,Cy) on the map. As I said before, I will occur there at the beginning of the day. When I set out from somewhere and leave for the next destination, I have two choices: on foot, or by taxi (don’t laugh at me anyway). My walking speed keeps at Vwalk km/h and it won’t change. However, car speed limit differs on every road due to the different traffic situations. Cars can only run along the roads rather than other areas, while walking is of no constraints.
If I choose to walk to the next destination, I go there directly along a straight line from start to target and will not stop on the way. But taking a taxi is a little bit complicated. Firstly I’ll choose a road, and walk to the nearest position from me on that road. If there’s a tie, all candidates are available. After waiting for a taxi for Twait minutes, I step on a taxi at that position and choose a road as my target. The car will run along the roads and send me to the target road, and I’ll get off the taxi at the nearest location to the destination on that road. Finally, I walk from where I get off the taxi along a straight way to the destination, and will not take another taxi any more (even it might be faster, but it costs money for me). Because of my urgent demands, the taxi always runs at limit speed on every specific road. But the taxi drivers are not well enough - I have to determine the way myself to prevent being ripped off.
N packages’ destinations spread all over the city. The ith package’s destination locates at Pi(xi,yi) which may occur at any corner of the city except on any roads. Besides, there’s an urgency degree for each package, denoted by Ui. Customers are always troubles, and hence my mission is certainly to try my best minimizing their dissatisfaction. If Package i arrives at the destination by ti minutes since I set off from the company, the specific customer’s dissatisfaction should be Ui * ti.
I’m going to minimize the sum of all dissatisfactions. How should I determine the order of deliveries and the tour plan to accomplish the mission?
Input
The input contains several test cases. The number of test cases T (T<=10) occurs in the first line of input.
For each test case:
The first line contains N , M , Vwalk and Twait.
The following line gives the company’s coordinates Cx,Cy .
The following N lines describe the packages, where the ith line contains xi,yi,Ui, indicating that package i locates at Pi(x, y) with a urgency degree Ui.
The following M lines describe the roads. Two formats are potential:
a)Line xiA yiA xiB yiB vi: line-shaped road whose endpoints are Ai(xiA,yiA) and Bi(xiB,yiB).
b)Circle xi yi Ri vi: circle-shaped road whose centre is Oi(xi, yi) with a radius of Ri.
Here, vi denotes the limit speed for the ith road, measured in km/h.
Scales:
1<=N<=15
1<=M<=30
0.01<=Vwalk<=10.00, 0.01<=vi<=120.00, 0.01<=Twait<=60.00
0.01<=Ui, Ri<=1000.00.
The coordinates, radius, time and speed are float numbers and will be rounded in 2 decimals. The absolute value of coordinates doesn’t exceed 1000.
Output
For each test case, output the minimal sum of dissatisfactions in a line, rounded in 2 decimals.
The test data guarantees that answers will not exceed 107.
Sample Input
1
2 5 6 0
3 1
3 0 1
-2 0 1
Circle 0 0 1 60
Line 1 0 2 0 60
Line 2 -1 2 1 60
Line 2 1 -2 1 60
Line 2 -1 -2 -1 60
Sample Output
44.14
