Minimum length of square to contain at least half of the given Coordinates

0 0 5 minutes read

Given a set of N points in the 2-D plane. The task is to find the minimum value of M such that a square centered at the origin with side 2*M contains at least floor(N/2) points inside or on it.

Examples:

Input : N = 4
Points are: {(1, 2), (-3, 4), (1, 78), (-3, -7)}
Output : 4
The square with end point (4, 4), (-4, -4), (4, -4), (-4, 4) will contain the points (1, 2) and (-3, 4).
Smallest Possible value of M such that the square has at least 2 points is 4.
Input : N = 3
Points are: {(1, 2), (-3, 4), (1, 78)}
Output : 2
Square contains the point (1, 2). {floor(3/2) = 1}

Approach:

One major observation for any point (x, y), minimum M in which this point lies is max(abs(x), abs(y)).
Using point 1. We can find the minimum value of M for all the points and store them in an array.
Sort the array.
Now, array[i] denotes minimum M such that if i points are required in the square of side 2*M. (as all the points below i have the minimum value of M less than or equal to i).
Print the value of array[floor(n/2)].

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to Calculate Absolute Value
int mod(int x)
{
    if (x >= 0)
        return x;
    return -x;
}
 
// Function to Calculate the Minimum value of M
void findSquare(int n)
{
    int points[n][2] = { { 1, 2 }, { -3, 4 }, 
                       { 1, 78 }, { -3, -7 } };
    int a[n];
 
    // To store the minimum M for each
    // point in array
    for (int i = 0; i < n; i++) {
        int x, y;
        x = points[i][0];
        y = points[i][1];
        a[i] = max(mod(x), mod(y));
    }
 
    // Sort the array
    sort(a, a + n);
 
    // Index at which atleast required point are
    // inside square of length 2*M
    int index = floor(n / 2) - 1;
    cout << "Minimum M required is: " << a[index] << endl;
}
 
// Driver Code
int main()
{
    int N;
    N = 4;
    findSquare(N);
 
    return 0;
}

Java

import java.util.*;
 
// Java program to find next identical year
class GFG
{
 
// Function to Calculate Absolute Value
static int mod(int x)
{
    if (x >= 0)
        return x;
    return -x;
}
 
// Function to Calculate the Minimum value of M
static void findSquare(int n)
{
    int points[][] = { { 1, 2 }, { -3, 4 }, 
                    { 1, 78 }, { -3, -7 } };
    int []a = new int[n];
 
    // To store the minimum M for each
    // point in array
    for (int i = 0; i < n; i++)
    {
        int x, y;
        x = points[i][0];
        y = points[i][1];
        a[i] = Math.max(mod(x), mod(y));
    }
 
    // Sort the array
    Arrays.sort(a);
 
    // Index at which atleast required point are
    // inside square of length 2*M
    int index = (int) (Math.floor(n / 2) - 1);
    System.out.println("Minimum M required is: " + a[index]);
}
 
// Driver Code
public static void main(String[] args) 
{
    int N;
    N = 4;
    findSquare(N);
}
}
 
// This code contributed by Rajput-Ji

Python3

# Python3 implementation of the
# above approach 
 
# Function to Calculate the 
# Minimum value of M 
def findSquare(n): 
 
    points = [[1, 2], [-3, 4], 
              [1, 78], [-3, -7]] 
    a = [None] * n 
 
    # To store the minimum M
    # for each point in array 
    for i in range(0, n): 
        x = points[i][0] 
        y = points[i][1] 
        a[i] = max(abs(x), abs(y)) 
     
    # Sort the array 
    a.sort() 
 
    # Index at which atleast required 
    # point are inside square of length 2*M 
    index = n // 2 - 1
    print("Minimum M required is:", a[index]) 
 
# Driver Code 
if __name__ == "__main__":
 
    N = 4
    findSquare(N)
     
# This code is contributed 
# by Rituraj Jain

C#

// C# program to find next identical year 
using System;
 
class GFG 
{ 
 
// Function to Calculate Absolute Value 
static int mod(int x) 
{ 
    if (x >= 0) 
        return x; 
    return -x; 
} 
 
// Function to Calculate the Minimum value of M 
static void findSquare(int n) 
{ 
    int [,]points = new int[4,2]{ { 1, 2 }, { -3, 4 }, 
                    { 1, 78 }, { -3, -7 } }; 
    int []a = new int[n]; 
 
    // To store the minimum M for each 
    // point in array 
    for (int i = 0; i < n; i++) 
    { 
        int x, y; 
        x = points[i,0]; 
        y = points[i,1]; 
        a[i] = Math.Max(mod(x), mod(y)); 
    } 
 
    // Sort the array 
    Array.Sort(a); 
 
    // Index at which atleast required point are 
    // inside square of length 2*M 
    int index = (int) (n / 2 - 1); 
    Console.WriteLine("Minimum M required is: " + a[index]); 
} 
 
// Driver Code 
public static void Main(String []args) 
{ 
    int N; 
    N = 4; 
    findSquare(N); 
} 
} 
 
// This code contributed by Arnab Kundu 

PHP

<?php
// PHP implementation of the above approach
 
// Function to Calculate Absolute Value
function mod($x)
{
    if ($x >= 0)
        return $x;
    return -$x;
}
 
// Function to Calculate the
// Minimum value of M
function findSquare($n)
{
    $points = array(array( 1, 2 ), 
                    array( -3, 4 ), 
                    array( 1, 78 ),
                    array( -3, -7 ));
    $a[$n] = array();
 
    // To store the minimum M for each
    // point in array
    for ($i = 0; $i < $n; $i++) 
    {
        $x; $y;
        $x = $points[$i][0];
        $y = $points[$i][1];
        $a[$i] = max(mod($x), mod($y));
    }
 
    // Sort the array
    sort($a);
 
    // Index at which atleast required point 
    // are inside square of length 2*M
    $index = floor($n / 2) - 1;
    echo "Minimum M required is: ", 
                  $a[$index], "\n";
}
 
// Driver Code
$N = 4;
findSquare($N);
 
// This code is contributed by ajit.
?>

Javascript

<script>
    // Javascript program to find next identical year
     
    // Function to Calculate Absolute Value
    function mod(x)
    {
        if (x >= 0)
            return x;
        return -x;
    }
 
    // Function to Calculate the Minimum value of M
    function findSquare(n)
    {
        let points = [ [ 1, 2 ], [ -3, 4 ], 
                        [ 1, 78 ], [ -3, -7 ] ];
        let a = new Array(n);
 
        // To store the minimum M for each
        // point in array
        for (let i = 0; i < n; i++)
        {
            let x, y;
            x = points[i][0];
            y = points[i][1];
            a[i] = Math.max(mod(x), mod(y));
        }
 
        // Sort the array
        a.sort(function(a, b){return a - b});
 
        // Index at which atleast required point are
        // inside square of length 2*M
        let index = (Math.floor(n / 2) - 1);
        document.write("Minimum M required is: " + a[index]);
    }
     
    let N;
    N = 4;
    findSquare(N);
 
         
</script>

Output:

Minimum M required is: 4

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!