Dados N puntos en un plano bidimensional. Se dice que un punto está por encima de otro punto si las coordenadas X de ambos puntos son iguales y la coordenada Y del primer punto es mayor que la coordenada Y del segundo punto. Del mismo modo, definimos abajo, izquierda y derecha. La tarea es contar el número de puntos que tienen al menos un punto arriba, abajo, a la izquierda oa la derecha.
Ejemplos:
Entrada: arr[] = {{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}}
Salida: 1
El único punto que satisface la condición es el punto (0, 0).
Entrada: arr[] = {{0, 0}, {1, 0}, {0, -2}, {5, 0}}
Salida: 0
Planteamiento: Para cada coordenada X , encuentre 2 valores, la coordenada Y mínima y máxima entre todos los puntos que tienen esta coordenada X. Haz lo mismo para cada coordenada Y. Ahora, para que un punto satisfaga las restricciones, su coordenada Y debe estar entre los 2 valores calculados para esa coordenada X. Compruebe lo mismo para su coordenada X.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MX 2001
#define OFF 1000
// Represents a point in 2-D space
struct point {
int x, y;
};
// Function to return the count of
// required points
int countPoints(int n, struct point points[])
{
int minx[MX];
int miny[MX];
// Initialize minimum values to infinity
fill(minx, minx + MX, INT_MAX);
fill(miny, miny + MX, INT_MAX);
// Initialize maximum values to zero
int maxx[MX] = { 0 };
int maxy[MX] = { 0 };
int x, y;
for (int i = 0; i < n; i++) {
// Add offset to deal with negative
// values
points[i].x += OFF;
points[i].y += OFF;
x = points[i].x;
y = points[i].y;
// Update the minimum and maximum
// values
minx[y] = min(minx[y], x);
maxx[y] = max(maxx[y], x);
miny[x] = min(miny[x], y);
maxy[x] = max(maxy[x], y);
}
int count = 0;
for (int i = 0; i < n; i++) {
x = points[i].x;
y = points[i].y;
// Check if condition is satisfied
// for X coordinate
if (x > minx[y] && x < maxx[y])
// Check if condition is satisfied
// for Y coordinate
if (y > miny[x] && y < maxy[x])
count++;
}
return count;
}
// Driver code
int main()
{
struct point points[] = { { 0, 0 },
{ 0, 1 },
{ 1, 0 },
{ 0, -1 },
{ -1, 0 } };
int n = sizeof(points) / sizeof(points[0]);
cout << countPoints(n, points);
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MX = 2001;
static int OFF = 1000;
// Represents a point in 2-D space
static class point
{
int x, y;
public point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// Function to return the count of
// required points
static int countPoints(int n, point points[])
{
int []minx = new int[MX];
int []miny = new int[MX];
// Initialize minimum values to infinity
for (int i = 0; i < n; i++)
{
minx[i]=Integer.MAX_VALUE;
miny[i]=Integer.MAX_VALUE;
}
// Initialize maximum values to zero
int []maxx = new int[MX];
int []maxy = new int[MX];
int x, y;
for (int i = 0; i < n; i++)
{
// Add offset to deal with negative
// values
points[i].x += OFF;
points[i].y += OFF;
x = points[i].x;
y = points[i].y;
// Update the minimum and maximum
// values
minx[y] = Math.min(minx[y], x);
maxx[y] = Math.max(maxx[y], x);
miny[x] = Math.min(miny[x], y);
maxy[x] = Math.max(maxy[x], y);
}
int count = 0;
for (int i = 0; i < n; i++)
{
x = points[i].x;
y = points[i].y;
// Check if condition is satisfied
// for X coordinate
if (x > minx[y] && x < maxx[y])
// Check if condition is satisfied
// for Y coordinate
if (y > miny[x] && y < maxy[x])
count++;
}
return count;
}
// Driver code
public static void main(String[] args)
{
point points[] = {new point(0, 0),
new point(0, 1),
new point(1, 0),
new point(0, -1),
new point(-1, 0)};
int n = points.length;
System.out.println(countPoints(n, points));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach from sys import maxsize as INT_MAX MX = 2001 OFF = 1000 # Represents a point in 2-D space class point: def __init__(self, x, y): self.x = x self.y = y # Function to return the count of # required points def countPoints(n: int, points: list) -> int: # Initialize minimum values to infinity minx = [INT_MAX] * MX miny = [INT_MAX] * MX # Initialize maximum values to zero maxx = [0] * MX maxy = [0] * MX x, y = 0, 0 for i in range(n): # Add offset to deal with negative # values points[i].x += OFF points[i].y += OFF x = points[i].x y = points[i].y # Update the minimum and maximum # values minx[y] = min(minx[y], x) maxx[y] = max(maxx[y], x) miny[x] = min(miny[x], y) maxy[x] = max(maxy[x], y) count = 0 for i in range(n): x = points[i].x y = points[i].y # Check if condition is satisfied # for X coordinate if (x > minx[y] and x < maxx[y]): # Check if condition is satisfied # for Y coordinate if (y > miny[x] and y < maxy[x]): count += 1 return count # Driver Code if __name__ == "__main__": points = [point(0, 0), point(0, 1), point(1, 0), point(0, -1), point(-1, 0)] n = len(points) print(countPoints(n, points)) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int MX = 2001;
static int OFF = 1000;
// Represents a point in 2-D space
public class point
{
public int x, y;
public point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// Function to return the count of
// required points
static int countPoints(int n, point []points)
{
int []minx = new int[MX];
int []miny = new int[MX];
// Initialize minimum values to infinity
for (int i = 0; i < n; i++)
{
minx[i]=int.MaxValue;
miny[i]=int.MaxValue;
}
// Initialize maximum values to zero
int []maxx = new int[MX];
int []maxy = new int[MX];
int x, y;
for (int i = 0; i < n; i++)
{
// Add offset to deal with negative
// values
points[i].x += OFF;
points[i].y += OFF;
x = points[i].x;
y = points[i].y;
// Update the minimum and maximum
// values
minx[y] = Math.Min(minx[y], x);
maxx[y] = Math.Max(maxx[y], x);
miny[x] = Math.Min(miny[x], y);
maxy[x] = Math.Max(maxy[x], y);
}
int count = 0;
for (int i = 0; i < n; i++)
{
x = points[i].x;
y = points[i].y;
// Check if condition is satisfied
// for X coordinate
if (x > minx[y] && x < maxx[y])
// Check if condition is satisfied
// for Y coordinate
if (y > miny[x] && y < maxy[x])
count++;
}
return count;
}
// Driver code
public static void Main(String[] args)
{
point []points = {new point(0, 0),
new point(0, 1),
new point(1, 0),
new point(0, -1),
new point(-1, 0)};
int n = points.Length;
Console.WriteLine(countPoints(n, points));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
var MX = 2001;
var OFF = 1000;
// Function to return the count of
// required points
function countPoints( n, points)
{
var minx = Array(MX).fill(1000000000);
var miny = Array(MX).fill(1000000000);
// Initialize maximum values to zero
var maxx = Array(MX).fill(0);
var maxy = Array(MX).fill(0);
var x, y;
for (var i = 0; i < n; i++) {
// Add offset to deal with negative
// values
points[i][0] += OFF;
points[i][1] += OFF;
x = points[i][0];
y = points[i][1];
// Update the minimum and maximum
// values
minx[y] = Math.min(minx[y], x);
maxx[y] = Math.max(maxx[y], x);
miny[x] = Math.min(miny[x], y);
maxy[x] = Math.max(maxy[x], y);
}
var count = 0;
for (var i = 0; i < n; i++) {
x = points[i][0];
y = points[i][1];
// Check if condition is satisfied
// for X coordinate
if (x > minx[y] && x < maxx[y])
// Check if condition is satisfied
// for Y coordinate
if (y > miny[x] && y < maxy[x])
count++;
}
return count;
}
// Driver code
var points = [ [ 0, 0 ],
[ 0, 1 ],
[ 1, 0 ],
[ 0, -1 ],
[ -1, 0 ] ];
var n = points.length;
document.write( countPoints(n, points));
// This code is contributed by famously.
</script>
Producción:
1
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA