The Optimal Super-Highway

In our real life when we look for help we find that only a few people are willing to help us but when we look for suggestions there are thousands waiting with their bag of suggestions. In the country named Culabura a similar situation is creating a lot of trouble. Culabura is a country containing around 20000 important places and infinite land area. The president of Culabura wants to build a super highway through his country. This super highway can be expressed by a straight line that fulfills the following two properties: a) It must be parallel to another road that connects the two most important cities (denoted by A and B) of the country. b) The summation of distances of all-important places from it must be minimum. The advisers of the king of Culabura are giving random and meaningless suggestions to solve this problem (As always is the case with advisers). Now your job is to find the minimum summation of distance. For example in the above picture you will have to find the minimum possible value of (d1 +d2 +d3 +d4 +d5 +d6 +d7 +d8). In other words you will have to place the superhighway in such a place so that (d1 +d2 +d3 +d4 +d5 +d6 +d7 +d8) is minimum and you will have print this minimum value. In this problem we will call such minimum value sum_d_min. Your solution must be very efficient. /*Looking for an O(n) solution */ Input The input file contains a single set of input. First line of each input set contains two integers N (0<N <20001)andQ(0<Q<101). HereN isthenumberofimportantplacesandQisthe

2/2 number of queries. Each of the next N lines contains a pair of integer xi and yi (|xi|, |yi| ≤ 100), where (xi, yi) is the coordinate of the i-th (0 ≤ i ≤ N − 1) important place. Each of the next Q lines contains four integers Ax, Ay, Bx, By, where (Ax,Ay) and (Bx,By) are the coordinates of A and B respectively and the optimal super highway must be parallel to street (or line) AB. You must not consider A and B as part of the N important places. Some important places may be present more than in the list to give them extra importance. You dont need to worry about that and just consider them as two different places. Also remember that place A and B will always be two different places. Output For each query produce one line of output. This line contains the serial of output followed by the value of sum_d_min for that particular query. All the output numbers should be rounded to nearest integer. Look at the output for sample input for details. Sample Input 62 11 1 10 20 12 24 11 24 10 10 11 11 2334 Sample Output Case 1: 15 Case 2: 15