Hello, Your Package!

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 A_i(x_iA,y_iA) and B_i(x_iB,y_iB) on a two-dimensional map, while a circle-shaped road should be expressed as a centre point O_i(x_i,y_i) 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 (C_x,C_y) 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 V_walk 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 T_wait 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 P_i(x_i,y_i) which may occur at any corner of the city except on any roads. Besides, there’s an urgency degree for each package, denoted by U_i. 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 t_i minutes since I set off from the company, the specific customer’s dissatisfaction should be U_i * t_i.

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?

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 , V_walk and T_wait.
The following line gives the company’s coordinates C_x,C_y .

The following N lines describe the packages, where the ith line contains x_i,y_i,U_i, indicating that package i locates at P_i(x, y) with a urgency degree U_i.

The following M lines describe the roads. Two formats are potential:
a)Line x_iA y_iA x_iB y_iB v_i: line-shaped road whose endpoints are A_i(x_iA,y_iA) and B_i(x_iB,y_iB).
b)Circle x_i y_i R_i v_i: circle-shaped road whose centre is O_i(x_i, y_i) with a radius of R_i.

Here, v_i denotes the limit speed for the ith road, measured in km/h.

Scales:
1<=N<=15
1<=M<=30
0.01<=V_walk<=10.00, 0.01<=v_i<=120.00, 0.01<=T_wait<=60.00
0.01<=U_i, R_i<=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.

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 10⁷.

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

44.14

BUPT

2014 Multi-University Training Contest 6