Dado un conjunto de N puntos en el plano 2-D. La tarea es encontrar el valor mínimo de M tal que un cuadrado con centro en el origen y lado 2*M contenga al menos puntos de suelo (N/2) dentro o sobre él.
Ejemplos:
Entrada: N = 4
Los puntos son: {(1, 2), (-3, 4), (1, 78), (-3, -7)}
Salida: 4
El cuadrado con punto final (4, 4), (-4, -4), (4, -4), (-4, 4) contendrán los puntos (1, 2) y (-3, 4).
El valor más pequeño posible de M tal que el cuadrado tiene al menos 2 puntos es 4.
Entrada: N = 3
Los puntos son: {(1, 2), (-3, 4), (1, 78)}
Salida: 2 El
cuadrado contiene el punto (1, 2). {piso (3/2) = 1}
Enfoque :
- Una observación importante para cualquier punto (x, y), mínimo M en el que se encuentra este punto es max(abs(x), abs(y)).
- Usando el punto 1. Podemos encontrar el valor mínimo de M para todos los puntos y almacenarlos en una array.
- Ordenar la array.
- Ahora, array[i] denota M mínimo tal que si se requieren i puntos en el cuadrado de lado 2*M. (ya que todos los puntos debajo de i tienen el valor mínimo de M menor o igual que i).
- Imprime el valor de array[piso(n/2)].
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Minimum M required is: 4
Complejidad de tiempo : O(n*log(n))
Espacio auxiliar : O(n)