5. There are N oil derricks in the area. The main oil pipeline will go through t
ID: 3733596 • Letter: 5
Question
5. There are N oil derricks in the area. The main oil pipeline will go through the area strictly from east to west, but its northern coordinate is negotiable. Each derrick must be connected directly to the main pipeline with its own pipe. Find the y-position of the main pipeline that will lead to minimal total length of all pipes coming from the derricks to this main pipeline. // input: xlil, yli] are the coordinates of each derrick // output: best y position of the main pipeline int bestY (int[] x, int[] y) The function should spend O(N log NExplanation / Answer
The problem statement is to find out the best y position for the main pipeline. it has noting to do with the x cordinate.
the solutionis to find out the median of the y coordinates. It will be the optimal solution.
so we need to sort the y cordinates and return the median of the sorted array. sort it using merge/quick sort.
int n = no_of_pipes;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int bestY(int[] x,int[] y){
mergeSort(y, 0, n - 1);
if(n%2 == 1) return y[n/2];
else return (y[n/2]+y[n/2+1])/2;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.