Plant LocationProblem code: K1 |
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!
Input
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.
Output
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.
Example
Input: 1 5 3 -5 -7 1 3 -2 4 4 -7 7 6 3 3 Output: 26.232349
Output details
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:
| Date: | 0000-00-00 |
| Time limit: | 3s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK TEXT JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Um, I am getting minimum
Um, I am getting minimum total distance less than given in example here. Am I wrong or the output shown here?? (26.xxxxxx), i am getting (22.xxxxxx).
Oh, sorry. It was my mistake.
Oh, sorry. It was my mistake. The output shown here is correct.
"None of these warehouses are
In the graph shown, optimum
In the graph shown, optimum location of plant P does not have integer cordinates. Is it not necessary for point P to have integer coordinates?
Why am i not getting output
Why am i not getting output accuratly. I am getting 26.xxxxxx but not precisely this answer and i am damn sure my logic is correct. Is there a way to make more precise calculations.
plz xplain the case(s) when
plz xplain the case(s) when the o/p will be NO
thnx........
Would you please elaborate on
Would you please elaborate on the line "If there is no optimum distance, print "NO" instead". At both the ends of the line, the distance tends to infinity. So there has to be at least one minima. How could there be no optimal distance ?
i m also unable to understand
i m also unable to understand the same ...............
plz xplain....
@rahul If you think there is
@rahul If you think there is always an answer, you won't have to print 'NO'. You may output the answer :)
@ Aniruddha : What I am
@ Aniruddha : What I am thinking of right now is that, my interpretation of the line "If there is no optimum distance, print "NO" instead" is incorrect :-) and this is the reason why I am constantly getting TLE.
Anyways, thanks for the reply.
Oops ! Sorry ! I means WA :)
Oops ! Sorry ! I means WA :)
can i get value of P , i
can i get value of P , i think my algo is write as p is is very close to the given p. but ans is a bit different
Someone plz reply to what
Someone plz reply to what Saurabh Singh has written. I am in a similar position.
I am getting 26.2XXXXX, but not exactly what the answer is given here.
Can someone atleast give the coordinates of P?
ans is a few start differing
ans is a few start differing from 2nd decimal place :(
@Admin can we discuss upon
@Admin
can we discuss upon value of p here ?
Come on someone let out the
Come on someone let out the value of P for this example . We are not getting answer becoz of this only . When u can tell output , what could be the problem in letting value of P out ?
And why does this site keep forgetting my password ?
Core2Due and i stuck in same
Core2Due and i stuck in same mess . My answer is also 26.2XXXXX.
@saurabh @Gunjan No, please
@saurabh @Gunjan No, please don't discuss specific values related to the answer. You are expected to work them out yourself.
Hey about the 'NO' thingy, i
Hey about the 'NO' thingy,
i think you can have 2 points with the same sum of distances, so u cant have a defenite answer
Does, " rounded to 6 decimal
Does, " rounded to 6 decimal places" mean if the answer is x.yyyyy66 it should be printed as x.yyyyy7 and if answer is x.yyyyy64 it should be printed as x.yyyyy6
i am the third person having
i am the third person having the same problem ....
my answer is not matching after 26.2XXXXX
..
well admin just a request ..
u have shown a sample output
it would be nice if u can supply the value of P for the sample output
will help us
thanks
Yes, it should be fine with
Yes, it should be fine with telling completely about the sample case, giving nothing more than the answer. ( point P and Tot.Distance ).
There is no need to be told
There is no need to be told the location of point P. The example is solely there so you can understand the problem; it is not meant to give you hints as to how to solve it.
Are the coordinates integers
Are the coordinates integers too?
Yes, please specify whether
Yes, please specify whether the coordinates are necessarily integer numbers or not.
The problem statement
The problem statement precisely describes the possible locations of the plant. Make no assumptions unless they are given to you explicitly.
running fine on my pc ....
running fine on my pc .... but giving runtime error here . ny help
obviously they are not
obviously they are not integers. and instead of asking others you could urself compute the coordinates. anyway i have greatly reduced the range but still stuck on TLE
I am also getting 26.2XXXXX
I am also getting 26.2XXXXX different from given answer and hence WA. Is the problem with precision?
can anyone give a "-1"
can anyone give a "-1" testcase ? thank
@Unni There cant be two
@Unni
There cant be two points giving the same distance(optimum)
Moreover if there exists more than 1 point giving the same distance(optimum), The task is to print the distance(optimum) and since since all points produce the same there will be nothing wrong in printing that distance