All submissions for this problem are available.
A new highway called Highway 1 has just been built in the Kingdom of Byteland. Ingoo, the largest CPU manufacturer in Byteland, would like to build a new chipset plant along the highway.
Ingoo currently has N warehouses in the kingdom. None of these warehouses are near the new highway. Chipsets manufactured from the new plant must be delivered to the warehouses. Thus, the further the distances from the new plant to the warehouses, the more the delivery cost Ingoo needs to bear.
Therefore, the CEO of Ingoo would like to find a place on Highway 1 to build the new plant in such a way that the total distance from the plant to all the warehouses is minimized.
You are visiting Byteland on December vacation and have decided to help Ingoo to locate the new plant!
The first line contains T (about 20), the number of test cases. Then T test cases follow. Each test case has the following form:
The first line contains a number N (1 <= N <= 2000), the number of Ingoo's warehouses.
The second line contains three integers A, B, C which describe the line equation (Ax+By+C=0) of Highway 1 (|A|, |B|, |C| <= 5000).
The next N lines contains the coordinates (x, y) of the warehouses (|x|, |y| <= 5000).
You are guaranteed that A, B, C form a valid line equation (i.e. A and B are not both 0) and no warehouses lie on Highway 1.
For each test case, print in a single line the minimum total distance between the new plant and all the warehouses, rounded to 6 decimal places. If there is no optimum distance, print "NO" instead.
Input: 1 5 3 -5 -7 1 3 -2 4 4 -7 7 6 3 3 Output: 26.232349
The line equation of Highway 1 is 3x-5x-7=0. Ingoo have 5 warehouses: A(1,3), B(-2,4), C(4,-7), D(7,6), and E(3,3). The optimum location of the new plant is P as shown in the figure below:
|Time Limit:||0.283 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.