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 Valueint mod(int x){ if (x >= 0) return x; return -x;}// Function to Calculate the Minimum value of Mvoid 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 Codeint main(){ int N; N = 4; findSquare(N); return 0;} |
Java
import java.util.*;// Java program to find next identical yearclass GFG{// Function to Calculate Absolute Valuestatic int mod(int x){ if (x >= 0) return x; return -x;}// Function to Calculate the Minimum value of Mstatic 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 Codepublic 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 Valuefunction mod($x){ if ($x >= 0) return $x; return -$x;}// Function to Calculate the// Minimum value of Mfunction 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Here you will find 53338 more Information to that Topic: geeksforgeeks.org/minimum-length-of-square-to-contain-at-least-half-of-the-given-coordinates/ […]