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)