Étant donné N points dans un espace bidimensionnel, nous devons trouver trois points tels que le triangle formé en choisissant ces points ne contienne aucun autre point à l'intérieur. Tous les points donnés ne se situeront pas sur la même ligne, donc la solution existera toujours.
Exemples :
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 solution est basée sur le fait que s’il existe un ou plusieurs triangles sans point à l’intérieur, nous pouvons former un triangle avec n’importe quel point aléatoire parmi tous les points.
Nous pouvons résoudre ce problème en recherchant les trois points un par un. Le premier point peut être choisi au hasard. Après avoir choisi le premier point, nous avons besoin de deux points tels que leur pente soit différente et qu’aucun point ne se trouve à l’intérieur du triangle de ces trois points. Nous pouvons le faire en choisissant le deuxième point comme point le plus proche du premier et le troisième point comme deuxième point le plus proche avec une pente différente. Pour ce faire, nous parcourons d’abord tous les points, choisissons le point le plus proche du premier et le désignons comme deuxième point du triangle requis. Ensuite, nous réitérons une fois de plus pour trouver le point qui a une pente différente et qui a la plus petite distance qui sera le troisième point de notre triangle.
acteur chiranjeeviC++
// C/C++ program to find triangle with no point inside #include
// 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.
# 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
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
<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]+'
'); document.write(points[second][0] + ' ' + points[second][1]+'
'); document.write(points[third][0] + ' ' + points[third][1]+'
'); } // 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>
Sortir:
0 0
1 1
0 2
Complexité temporelle : Sur)
Espace auxiliaire : O(1)
Cet article est rédigé par Utkarsh Trivedi .
Approche n°2 : Utiliser la force brute
Ce code parcourt tous les triangles possibles qui peuvent être formés à partir de l'ensemble de points donné et vérifie si un autre point se trouve à l'intérieur de chaque triangle. Si un triangle est trouvé où aucun point ne se trouve à l’intérieur, le code renvoie le triangle. Sinon, il renvoie Aucun.
Algorithme
1. Parcourez tous les triangles possibles avec des sommets à partir des points donnés.
2. Pour chaque triangle, vérifiez si l'un des points restants se trouve à l'intérieur du triangle.
3. Si aucun point ne se trouve à l’intérieur d’un triangle, renvoyez les coordonnées du premier triangle trouvé.
#include
import java.util.ArrayList; import java.util.List; public class Main { static double area(int x1 int y1 int x2 int y2 int x3 int y3) { return Math.abs((x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))/2.0); } static boolean isInsideTriangle(int x1 int y1 int x2 int y2 int x3 int y3 int x int y) { double A = area(x1 y1 x2 y2 x3 y3); double A1 = area(x y x2 y2 x3 y3); double A2 = area(x1 y1 x y x3 y3); double A3 = area(x1 y1 x2 y2 x y); return A == A1 + A2 + A3; } static List<List<Integer>> noPointInsideTriangle(List<List<Integer>> points) { for (int i = 0; i < points.size(); i++) { for (int j = i+1; j < points.size(); j++) { for (int k = j+1; k < points.size(); k++) { boolean inside = false; for (int l = 0; l < points.size(); l++) { if (l != i && l != j && l != k) { if (isInsideTriangle(points.get(i).get(0) points.get(i).get(1) points.get(j).get(0) points.get(j).get(1) points.get(k).get(0) points.get(k).get(1) points.get(l).get(0) points.get(l).get(1))) { inside = true; break; } } } if (!inside) { List<List<Integer>> result = new ArrayList<>(); result.add(points.get(i)); result.add(points.get(j)); result.add(points.get(k)); return result; } } } } return null; } public static void main(String[] args) { List<List<Integer>> points = new ArrayList<>(); points.add(new ArrayList<Integer>(){{add(0); add(0);}}); points.add(new ArrayList<Integer>(){{add(0); add(2);}}); points.add(new ArrayList<Integer>(){{add(2); add(0);}}); points.add(new ArrayList<Integer>(){{add(2); add(2);}}); points.add(new ArrayList<Integer>(){{add(1); add(1);}}); List<List<Integer>> result = noPointInsideTriangle(points); if (result != null) { System.out.println(result); } else { System.out.println('No triangle found.'); } } }
def area(x1 y1 x2 y2 x3 y3): return abs((x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))/2.0) def is_inside_triangle(x1 y1 x2 y2 x3 y3 x y): A = area(x1 y1 x2 y2 x3 y3) A1 = area(x y x2 y2 x3 y3) A2 = area(x1 y1 x y x3 y3) A3 = area(x1 y1 x2 y2 x y) return A == A1 + A2 + A3 def no_point_inside_triangle(points): for i in range(len(points)): for j in range(i+1 len(points)): for k in range(j+1 len(points)): inside = False for l in range(len(points)): if l != i and l != j and l != k: if is_inside_triangle(points[i][0] points[i][1] points[j][0] points[j][1] points[k][0] points[k][1] points[l][0] points[l][1]): inside = True break if not inside: return [points[i] points[j] points[k]] return None # Example usage points = [[0 0] [0 2] [2 0] [2 2] [1 1]] print(no_point_inside_triangle(points))
using System; using System.Collections.Generic; class Program { // Function to calculate the area of a triangle given its three vertices static double Area(double x1 double y1 double x2 double y2 double x3 double y3) { return Math.Abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0); } // Function to check if a point (x y) is inside a triangle defined by its vertices (x1 y1) (x2 y2) and (x3 y3) static bool IsInsideTriangle(double x1 double y1 double x2 double y2 double x3 double y3 double x double y) { double A = Area(x1 y1 x2 y2 x3 y3); double A1 = Area(x y x2 y2 x3 y3); double A2 = Area(x1 y1 x y x3 y3); double A3 = Area(x1 y1 x2 y2 x y); return Math.Abs(A - (A1 + A2 + A3)) < 1e-9; // Use a small epsilon value for comparison due to floating-point precision } // Function to find three points from a list that do not form a triangle with any other point inside static List<double[]> NoPointInsideTriangle(List<double[]> points) { for (int i = 0; i < points.Count; ++i) { for (int j = i + 1; j < points.Count; ++j) { for (int k = j + 1; k < points.Count; ++k) { bool inside = false; for (int l = 0; l < points.Count; ++l) { if (l != i && l != j && l != k) { if (IsInsideTriangle(points[i][0] points[i][1] points[j][0] points[j][1] points[k][0] points[k][1] points[l][0] points[l][1])) { inside = true; break; } } } if (!inside) { List<double[]> result = new List<double[]> { points[i] points[j] points[k] }; return result; } } } } return new List<double[]>(); // Return an empty list if no such set of points is found } static void Main(string[] args) { List<double[]> points = new List<double[]> { new double[] {0 0} new double[] {0 2} new double[] {2 0} new double[] {2 2} new double[] {1 1} }; List<double[]> result = NoPointInsideTriangle(points); if (result.Count > 0) { Console.WriteLine('Points that do not form a triangle with any other point inside:'); foreach (var point in result) { Console.WriteLine($'({point[0]} {point[1]})'); } } else { Console.WriteLine('No such set of points found.'); } } }
// JavaScript equivalent of the Python code above function area(x1 y1 x2 y2 x3 y3) { return Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0); } function is_inside_triangle(x1 y1 x2 y2 x3 y3 x y) { const A = area(x1 y1 x2 y2 x3 y3); const A1 = area(x y x2 y2 x3 y3); const A2 = area(x1 y1 x y x3 y3); const A3 = area(x1 y1 x2 y2 x y); return A === A1 + A2 + A3; } function no_point_inside_triangle(points) { for (let i = 0; i < points.length; i++) { for (let j = i + 1; j < points.length; j++) { for (let k = j + 1; k < points.length; k++) { let inside = false; for (let l = 0; l < points.length; l++) { if (l !== i && l !== j && l !== k) { if (is_inside_triangle(points[i][0] points[i][1] points[j][0] points[j][1] points[k][0] points[k][1] points[l][0] points[l][1])) { inside = true; break; } } } if (!inside) { return [points[i] points[j] points[k]]; } } } } return null; } // Example usage const points = [[0 0] [0 2] [2 0] [2 2] [1 1]]; console.log(no_point_inside_triangle(points));
Sortir
[[0 0] [0 2] [1 1]]
Complexité temporelle : O(n^4) où n est le nombre de points. En effet, nous devons parcourir tous les triangles possibles qui sont n, choisissez 3, puis vérifier si chacun des points restants se trouve à l'intérieur du triangle qui est O(n).
Complexité spatiale : O(1) puisque nous ne stockons que quelques variables à la fois.
Créer un quiz