Problem E
The Optimal Super Highway
Input: standard input
Output: standard output
Time Limit: 1 second
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 */
The input file contains a single set of input. First line of each input set contains two integers N (0<N<20001) and Q(0<Q<101). Here N is the number of important places and Q is the 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 don’t 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.
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.
6 2 1 1 1 10 20 12 2 4 1 1 2 4 10 10 11 11 2 3 3 4 |
Case
1: 15 Case
2: 15 |
Problem setter: Shahriar Manzoor, EPS