Dados N puntos en un espacio bidimensional, necesitamos encontrar tres puntos tales que el triángulo formado al elegir estos puntos no deba contener ningún otro punto dentro. Todos los puntos dados no estarán en la misma línea, por lo que siempre existirá una solución.
Ejemplos:
In above diagram possible triangle with no point inside can be formed by choosing these triplets, [(0, 0), (2, 0), (1, 1)] [(0, 0), (1, 1), (0, 2)] [(1, 1), (2, 0), (2, 2)] [(1, 1), (0, 2), (2, 2)] So any of the above triplets can be the final answer.
La solución se basa en el hecho de que si existen triángulos sin puntos dentro, entonces podemos formar un triángulo con cualquier punto al azar entre todos los puntos.
Podemos resolver este problema buscando los tres puntos uno por uno. El primer punto se puede elegir al azar. Después de elegir el primer punto, necesitamos dos puntos de modo que su pendiente sea diferente y ningún punto debe estar dentro del triángulo de estos tres puntos. Podemos hacer esto eligiendo el segundo punto como el punto más cercano al primero y el tercer punto como el segundo punto más cercano con la pendiente diferente. Para hacer esto, primero iteramos sobre todos los puntos y elegimos el punto más cercano al primero y lo designamos como el segundo punto del triángulo requerido. Luego iteramos una vez más para encontrar el punto que tiene una pendiente diferente y la distancia más pequeña, que será el tercer punto de nuestro triángulo.
C++
// C/C++ program to find triangle with no point inside
#include <bits/stdc++.h>
using namespace std;
// method to get square of distance between
// (x1, y1) and (x2, y2)
int getDistance(int x1, int y1, int x2, int y2)
{
return (x2 - x1)*(x2 - x1) +
(y2 - y1)*(y2 - y1);
}
// Method prints points which make triangle with no
// point inside
void triangleWithNoPointInside(int points[][2], int N)
{
// any point can be chosen as first point of triangle
int first = 0;
int second, third;
int minD = INT_MAX;
// choose nearest point as second point of triangle
for (int i = 0; i < N; i++)
{
if (i == first)
continue;
// Get distance from first point and choose
// nearest one
int d = getDistance(points[i][0], points[i][1],
points[first][0], points[first][1]);
if (minD > d)
{
minD = d;
second = i;
}
}
// Pick third point by finding the second closest
// point with different slope.
minD = INT_MAX;
for (int i = 0; i < N; i++)
{
// if already chosen point then skip them
if (i == first || i == second)
continue;
// get distance from first point
int d = getDistance(points[i][0], points[i][1],
points[first][0], points[first][1]);
/* the slope of the third point with the first
point should not be equal to the slope of
second point with first point (otherwise
they'll be collinear) and among all such
points, we choose point with the smallest
distance */
// here cross multiplication is compared instead
// of division comparison
if ((points[i][0] - points[first][0]) *
(points[second][1] - points[first][1]) !=
(points[second][0] - points[first][0]) *
(points[i][1] - points[first][1]) &&
minD > d)
{
minD = d;
third = i;
}
}
cout << points[first][0] << ", "
<< points[first][1] << endl;
cout << points[second][0] << ", "
<< points[second][1] << endl;
cout << points[third][0] << ", "
<< points[third][1] << endl;
}
// Driver code to test above methods
int main()
{
int points[][2] = {{0, 0}, {0, 2}, {2, 0},
{2, 2}, {1, 1}};
int N = sizeof(points) / sizeof(points[0]);
triangleWithNoPointInside(points, N);
return 0;
}
Java
// Java program to find triangle
// with no point inside
import java.io.*;
class GFG
{
// method to get square of distance between
// (x1, y1) and (x2, y2)
static int getDistance(int x1, int y1, int x2, int y2)
{
return (x2 - x1)*(x2 - x1) +
(y2 - y1)*(y2 - y1);
}
// Method prints points which make triangle with no
// point inside
static void triangleWithNoPointInside(int points[][], int N)
{
// any point can be chosen as first point of triangle
int first = 0;
int second =0;
int third =0;
int minD = Integer.MAX_VALUE;
// choose nearest point as second point of triangle
for (int i = 0; i < N; i++)
{
if (i == first)
continue;
// Get distance from first point and choose
// nearest one
int d = getDistance(points[i][0], points[i][1],
points[first][0], points[first][1]);
if (minD > d)
{
minD = d;
second = i;
}
}
// Pick third point by finding the second closest
// point with different slope.
minD = Integer.MAX_VALUE;
for (int i = 0; i < N; i++)
{
// if already chosen point then skip them
if (i == first || i == second)
continue;
// get distance from first point
int d = getDistance(points[i][0], points[i][1],
points[first][0], points[first][1]);
/* the slope of the third point with the first
point should not be equal to the slope of
second point with first point (otherwise
they'll be collinear) and among all such
points, we choose point with the smallest
distance */
// here cross multiplication is compared instead
// of division comparison
if ((points[i][0] - points[first][0]) *
(points[second][1] - points[first][1]) !=
(points[second][0] - points[first][0]) *
(points[i][1] - points[first][1]) &&
minD > d)
{
minD = d;
third = i;
}
}
System.out.println(points[first][0] + ", "
+ points[first][1]);
System.out.println(points[second][0]+ ", "
+ points[second][1]) ;
System.out.println(points[third][0] +", "
+ points[third][1]);
}
// Driver code
public static void main (String[] args)
{
int points[][] = {{0, 0}, {0, 2}, {2, 0},
{2, 2}, {1, 1}};
int N = points.length;
triangleWithNoPointInside(points, N);
}
}
// This article is contributed by vt_m.
Python 3
# Python3 program to find triangle # with no point inside import sys # method to get square of distance between # (x1, y1) and (x2, y2) def getDistance(x1, y1, x2, y2): return (x2 - x1) * (x2 - x1) + \ (y2 - y1) * (y2 - y1) # Method prints points which make triangle # with no point inside def triangleWithNoPointInside(points, N): # any point can be chosen as # first point of triangle first = 0 second = 0 third = 0 minD = sys.maxsize # choose nearest point as # second point of triangle for i in range(0, N): if i == first: continue # Get distance from first point and choose # nearest one d = getDistance(points[i][0], points[i][1], points[first][0], points[first][1]) if minD > d: minD = d second = i # Pick third point by finding the second closest # point with different slope. minD = sys.maxsize for i in range (0, N): # if already chosen point then skip them if i == first or i == second: continue # get distance from first point d = getDistance(points[i][0], points[i][1], points[first][0], points[first][1]) """ the slope of the third point with the first point should not be equal to the slope of second point with first point (otherwise they'll be collinear) and among all such points, we choose point with the smallest distance """ # here cross multiplication is compared instead # of division comparison if ((points[i][0] - points[first][0]) * (points[second][1] - points[first][1]) != (points[second][0] - points[first][0]) * (points[i][1] - points[first][1]) and minD > d) : minD = d third = i print(points[first][0], ', ', points[first][1]) print(points[second][0], ', ', points[second][1]) print(points[third][0], ', ', points[third][1]) # Driver code points = [[0, 0], [0, 2], [2, 0], [2, 2], [1, 1]] N = len(points) triangleWithNoPointInside(points, N) # This code is contributed by Gowtham Yuvaraj
C#
using System;
// C# program to find triangle
// with no point inside
public class GFG
{
// method to get square of distance between
// (x1, y1) and (x2, y2)
public static int getDistance(int x1, int y1, int x2, int y2)
{
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}
// Method prints points which make triangle with no
// point inside
public static void triangleWithNoPointInside(int[][] points, int N)
{
// any point can be chosen as first point of triangle
int first = 0;
int second = 0;
int third = 0;
int minD = int.MaxValue;
// choose nearest point as second point of triangle
for (int i = 0; i < N; i++)
{
if (i == first)
{
continue;
}
// Get distance from first point and choose
// nearest one
int d = getDistance(points[i][0], points[i][1], points[first][0], points[first][1]);
if (minD > d)
{
minD = d;
second = i;
}
}
// Pick third point by finding the second closest
// point with different slope.
minD = int.MaxValue;
for (int i = 0; i < N; i++)
{
// if already chosen point then skip them
if (i == first || i == second)
{
continue;
}
// get distance from first point
int d = getDistance(points[i][0], points[i][1], points[first][0], points[first][1]);
/* the slope of the third point with the first
point should not be equal to the slope of
second point with first point (otherwise
they'll be collinear) and among all such
points, we choose point with the smallest
distance */
// here cross multiplication is compared instead
// of division comparison
if ((points[i][0] - points[first][0]) * (points[second][1] - points[first][1]) != (points[second][0] - points[first][0]) * (points[i][1] - points[first][1]) && minD > d)
{
minD = d;
third = i;
}
}
Console.WriteLine(points[first][0] + ", " + points[first][1]);
Console.WriteLine(points[second][0] + ", " + points[second][1]);
Console.WriteLine(points[third][0] + ", " + points[third][1]);
}
// Driver code
public static void Main(string[] args)
{
int[][] points = new int[][]
{
new int[] {0, 0},
new int[] {0, 2},
new int[] {2, 0},
new int[] {2, 2},
new int[] {1, 1}
};
int N = points.Length;
triangleWithNoPointInside(points, N);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript program to find triangle
// with no point inside
// method to get square of distance between
// (x1, y1) and (x2, y2)
function getDistance(x1 , y1 , x2 , y2) {
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}
// Method prints points which make triangle with no
// point inside
function triangleWithNoPointInside(points , N) {
// any point can be chosen as first point of triangle
var first = 0;
var second = 0;
var third = 0;
var minD = Number.MAX_VALUE;
// choose nearest point as second point of triangle
for (i = 0; i < N; i++) {
if (i == first)
continue;
// Get distance from first point and choose
// nearest one
var d = getDistance(points[i][0], points[i][1], points[first][0], points[first][1]);
if (minD > d) {
minD = d;
second = i;
}
}
// Pick third point by finding the second closest
// point with different slope.
minD = Number.MAX_VALUE;
for (i = 0; i < N; i++) {
// if already chosen point then skip them
if (i == first || i == second)
continue;
// get distance from first point
var d = getDistance(points[i][0], points[i][1], points[first][0], points[first][1]);
/*
* the slope of the third point with the first point should not be equal to the
* slope of second point with first point (otherwise they'll be collinear) and
* among all such points, we choose point with the smallest distance
*/
// here cross multiplication is compared instead
// of division comparison
if ((points[i][0] - points[first][0])
* (points[second][1] - points[first][1]) != (points[second][0] - points[first][0])
* (points[i][1] - points[first][1])
&& minD > d) {
minD = d;
third = i;
}
}
document.write(points[first][0] + ", " + points[first][1]+"<br/>");
document.write(points[second][0] + ", " + points[second][1]+"<br/>");
document.write(points[third][0] + ", " + points[third][1]+"<br/>");
}
// Driver code
var points = [ [ 0, 0 ], [ 0, 2 ], [ 2, 0 ], [ 2, 2 ], [ 1, 1 ] ];
var N = points.length;
triangleWithNoPointInside(points, N);
// This code contributed by umadevi9616
</script>
Producción:
0, 0 1, 1 0, 2
Complejidad temporal: O(n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA