Horje
Maximum the value of a given expression for any pair of coordinates on a 2D plane

Given a sorted 2D array arr[][2] of size N such that (arr[i][0], arr[i][1]) represents the coordinates of ith point in the cartesian plane and an integer K, the task is to find the maximum value of the expression (|arr[i][0] – arr[j][0]| + arr[i][1] + arr[j][1]) such that |arr[i][0] – arr[j][0]| ? K for any possible pair of coordinates (i, j).

Examples:

Input: arr[][] = {{1, 3}, {2, 0}, {5, 10}, {6, -10}}, K = 1
Output: 4
Explanation:
Choose pairs (0, 1). Now the value of the expression is given by:
value = (abs(1 – 2) + 3 + 0) = 4, which is maximum and abs(1 – 2) = 1(? K).
Therefore, print 4.

Input: arr[][] = {{0, 0}, {3, 0}, {9, 2}}, K = 3
Output: 3

Approach: The given problem can be solved using a Greedy Algorithm using the priority queue which is based on the following observations: 

  • Rearranging the expression for all i > j as (arr[i][0] – arr[i][1] + arr[j][0] + arr[j][1]).
  • Now, keeping the pair of {arr[i]x – arr[i]y, arr[i]x} in sorted order, the value of the given expression for every array element at index j can be calculated.

Follow the steps below to solve the problem:

  • Initialize a priority_queue of pairs say PQ that stores the pair of differences of coordinated axes of a point and X coordinate of that point.
  • Initialize a variable say res as INT_MIN to store the maximum value.
  • Traverse the array arr[][] and considering {X, Y} is the current point perform the following operations:
    • Iterate while PQ is not empty and (X – PQ.top()[1]) is greater than K and remove the top element from the priority_queue PQ.
    • If PQ is not empty then update the value of res as the maximum of res and PQ.top()[0] + X + Y).
    • Push the pair {Y – X, X} into the priority_queue PQ.
  • After completing the above steps, print the value of res as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum value
// of the given expression possible
// for any pair of co-ordinates
void findMaxValueOfEquation(
    vector<vector<int> >& arr, int K)
{
    // Stores the differences between pairs
    priority_queue<vector<int> > pq;
 
    // Stores the maximum value
    int res = INT_MIN;
 
    // Traverse the array arr[][]
    for (auto point : arr) {
 
        // While pq is not empty and
        // difference between point[0]
        // and pq.top()[1] > K
        while (!pq.empty()
               && point[0] - pq.top()[1]
                      > K) {
 
            // Removes the top element
            pq.pop();
        }
 
        // If pq is not empty
        if (!pq.empty()) {
 
            // Update the value res
            res = max(res,
                      pq.top()[0] + point[0] + point[1]);
        }
 
        // Push pair {point[1] - point[0],
        // point[0]} in pq
        pq.push({ point[1] - point[0],
                  point[0] });
    }
 
    // Print the result
    cout << res;
}
 
// Driver Code
int main()
{
    vector<vector<int> > arr
        = { { 1, 3 }, { 2, 0 },
            { 5, 10 }, { 6, -10 } };
    int K = 1;
    findMaxValueOfEquation(arr, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG
{
 
    // Function to find the maximum value
    // of the given expression possible
    // for any pair of co-ordinates
    static void findMaxValueOfEquation(int arr[][], int K)
    {
       
        // Stores the differences between pairs
        PriorityQueue<int[]> pq
            = new PriorityQueue<>((a, b) -> {
                  if (a[0] != b[0])
                      return b[0] - a[0];
                  return b[1] - a[1];
              });
 
        // Stores the maximum value
        int res = Integer.MIN_VALUE;
 
        // Traverse the array arr[][]
        for (int point[] : arr) {
 
            // While pq is not empty and
            // difference between point[0]
            // and pq.top()[1] > K
            while (!pq.isEmpty()
                   && point[0] - pq.peek()[1] > K) {
 
                // Removes the top element
                pq.poll();
            }
 
            // If pq is not empty
            if (!pq.isEmpty()) {
 
                // Update the value res
                res = Math.max(res, pq.peek()[0] + point[0]
                                        + point[1]);
            }
 
            // Push pair {point[1] - point[0],
            // point[0]} in pq
            pq.add(new int[] { point[1] - point[0],
                               point[0] });
        }
 
        // Print the result
        System.out.println(res);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int[][] arr
            = { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } };
        int K = 1;
        findMaxValueOfEquation(arr, K);
    }
}
 
// This code is contributed by Kingash.

Python3

# Python3 program for the above approach
 
# Function to find the maximum value
# of the given expression possible
# for any pair of co-ordinates
def findMaxValueOfEquation(arr, K):
   
    # Stores the differences between pairs
    pq = []
 
    # Stores the maximum value
    res = -10**8
 
    # Traverse the array arr[][]
    for point in arr:
 
        # While pq is not empty and
        # difference between point[0]
        # and pq.top()[1] > K
        while (len(pq)>0 and point[0] - pq[-1][1] > K):
           
            # Removes the top element
            del pq[-1]
 
        # If pq is not empty
        if (len(pq) > 0):
            # Update the value res
            res = max(res, pq[-1][0] + point[0] + point[1])
 
        # Push pair {point[1] - point[0],
        # point[0]} in pq
        pq.append([point[1] - point[0], point[0]])
        pq = sorted(pq)
 
    # Print the result
    print (res)
 
# Driver Code
if __name__ == '__main__':
    arr = [ [ 1, 3 ], [ 2, 0 ], [ 5, 10 ], [ 6, -10 ] ]
    K = 1
    findMaxValueOfEquation(arr, K)
 
# This code is contributed by mohit kumar 29.

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
class Program {
  static void FindMaxValueOfEquation(int[][] arr, int K)
  {
    // Stores the differences between pairs
    var pq = new SortedSet<int[]>(
      Comparer<int[]>.Create((a, b) => {
        if (a[0] != b[0]) {
          return b[0] - a[0];
        }
        return b[1] - a[1];
      }));
 
    // Stores the maximum value
    int res = int.MinValue;
 
    // Traverse the array arr[][]
    foreach(int[] point in arr)
    {
      // While pq is not empty and
      // difference between point[0]
      // and pq.top()[1] > K
      while (pq.Count > 0
             && point[0] - pq.Min[1] > K) {
        // Removes the top element
        pq.Remove(pq.Min);
      }
 
      // If pq is not empty
      if (pq.Count > 0) {
        // Update the value res
        res = Math.Max(res, pq.Min[0] + point[0]
                       + point[1]);
      }
 
      // Push pair {point[1] - point[0],
      // point[0]} in pq
      pq.Add(new int[] { point[1] - point[0],
                        point[0] });
    }
 
    // Print the result
    Console.WriteLine(res);
  }
 
  static void Main(string[] args)
  {
    int[][] arr
      = { new int[] { 1, 3 }, new int[] { 2, 0 },
         new int[] { 5, 10 }, new int[] { 6, -10 } };
    int K = 1;
    FindMaxValueOfEquation(arr, K);
  }
}
 
// This code is contributed by phasing17

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the maximum value
    // of the given expression possible
    // for any pair of co-ordinates
function findMaxValueOfEquation(arr,K)
{
 
    // Stores the differences between pairs
        let pq=[];
  
        // Stores the maximum value
        let res = Number.MIN_VALUE;
  
        // Traverse the array arr[][]
        for (let point=0;point< arr.length;point++) {
  
            // While pq is not empty and
            // difference between point[0]
            // and pq.top()[1] > K
            while (pq.length!=0
                   && arr[point][0] - pq[0][1] > K) {
  
                // Removes the top element
                pq.shift();
            }
  
            // If pq is not empty
            if (pq.length!=0) {
  
                // Update the value res
                res = Math.max(res, pq[0][0] + arr[point][0]
                                        + arr[point][1]);
            }
  
            // Push pair {point[1] - point[0],
            // point[0]} in pq
            pq.push([ arr[point][1] - arr[point][0],
                               arr[point][0] ]);
             
            pq.sort(function(a,b){
                    if (a[0] != b[0])
                      return b[0] - a[0];
                  return b[1] - a[1];})
        }
  
        // Print the result
        document.write(res);
}
 
// Driver Code
let arr = [[ 1, 3 ], [ 2, 0 ], [ 5, 10 ], [ 6, -10 ]];
let K = 1;
findMaxValueOfEquation(arr, K);
 
// This code is contributed by unknown2108
</script>

Output: 

4

 

Time Complexity: O(N * log N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Geometric

Related
Check if a point is inside, outside or on a Hyperbola Check if a point is inside, outside or on a Hyperbola
Minimum area of the triangle formed by any tangent to an ellipse with the coordinate axes Minimum area of the triangle formed by any tangent to an ellipse with the coordinate axes
Maximize count of intersecting line segments Maximize count of intersecting line segments
Program to calculate angle between two N-Dimensional vectors Program to calculate angle between two N-Dimensional vectors
Program to find Length of Latus Rectum of an Ellipse Program to find Length of Latus Rectum of an Ellipse

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje