Given opposing and candidate positions plus rebound spot probabilities, choose 5 of n candidate spots to maximize expected points from the resulting fast-break race.
Medium6Brute forceCombinatoricsGeometrySimulationNo attempts yetTime limit2sMemory limit512 MBThe court is a rectangle whose opposite corners are (0.0,0.0) and (94.0,50.0), measured in feet. Your team defends the basket at (0.0,25.0) and attacks the basket at (94.0,25.0).
When a shot misses, the ball bounces off the rim and lands somewhere on the court. You know m possible landing spots and the probability that the ball goes to each one. The five opposing players stand at fixed positions. Your team picks 5 of n candidate positions and puts one player on each of them.
Once the ball lands on a spot, the player closest to that spot among all 10 players on the court picks it up. That player runs in a straight line to the spot, takes the ball, then runs in a straight line to the basket that the player's own team attacks. At the same moment, the five players of the other team run in a straight line to the basket that their own team defends. Every player runs at 20 feet per second.
Let t be the number of seconds by which the player with the ball reaches the basket ahead of the fastest defender. If a defender arrives first, t is negative. The probability of scoring is 1−2−(t+1) when t≥0 and 2t−1 when t<0. A made basket is worth 2 points.
A basket by your team counts as +2 points and a basket by the other team counts as −2 points. Choose the 5 candidate positions that maximize the expected number of points, and report that expected value.
The first line contains the number of data sets K, with 1≤K≤20. K data sets follow.
The first line of a data set contains two integers n and m. n is the number of candidate positions for your players, with 5≤n≤15, and m is the number of possible landing spots, with 1≤m≤100.
The next line contains 10 real numbers x1−,y1−,…,x5−,y5−, the positions of the five opposing players. The next line contains 2n real numbers xj+,yj+, the candidate positions for your players. The last line contains 3m real numbers forming m triples (xk∘,yk∘,pk). The first two values of a triple are the coordinates of the k-th landing spot, and pk is the probability that the ball goes there.
Every x coordinate is between 0 and 94, and every y coordinate is between 0 and 50. Each pk is between 0 and 1, and ∑kpk=1. Whichever landing spot you take, no two of the 5 opposing positions and the n candidate positions have distances to it that differ by less than 0.001, so the player who picks the ball up is always unique.
For each data set, print Data Set x: on a line by itself, where x is the number of the data set counting from 1. On the next line, print the maximum expected number of points, rounded to two decimal places. Print one blank line after each data set.
If the rounded value is zero, print 0.00 and not -0.00. The exact answer is farther than 10−6 from any midpoint between two values with two decimal places.