2차원 공간에 N개의 점이 주어지면 우리는 이 점을 선택하여 만든 삼각형이 내부에 다른 점을 포함하지 않도록 세 개의 점을 찾아야 합니다. 주어진 모든 점이 같은 선상에 있지 않으므로 해는 항상 존재합니다.
예:
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.
해결책은 내부에 점이 없는 삼각형이 있는 경우 모든 점 중에서 임의의 점이 있는 삼각형을 형성할 수 있다는 사실에 기초합니다.
세 지점을 모두 하나씩 검색하면 이 문제를 해결할 수 있습니다. 첫 번째 포인트는 무작위로 선택될 수 있습니다. 첫 번째 점을 선택한 후에는 기울기가 달라야 하고 이 세 점의 삼각형 안에 점이 없어야 하는 두 점이 필요합니다. 두 번째 점을 가장 가까운 점으로 선택하고 첫 번째 점과 세 번째 점을 기울기가 다른 두 번째로 가까운 점으로 선택하면 됩니다. 이를 위해 먼저 모든 점을 반복하고 첫 번째 점에 가장 가까운 점을 선택하고 이를 필요한 삼각형의 두 번째 점으로 지정합니다. 그런 다음 한 번 더 반복하여 기울기가 다르고 거리가 가장 작은 점을 찾아 삼각형의 세 번째 점이 됩니다.
파이썬 정렬 사전C++
// 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>
산출:
0 0
1 1
0 2
시간 복잡도: 에)
보조 공간: 오(1)
이 기사는 기고자: 우트카르시 트리베디 .
접근법#2: 무차별 대입 사용
이 코드는 주어진 점 세트에서 형성될 수 있는 모든 가능한 삼각형을 반복하고 각 삼각형 내부에 다른 점이 있는지 확인합니다. 내부에 점이 없는 삼각형이 발견되면 코드는 삼각형을 반환합니다. 그렇지 않으면 None을 반환합니다.
연산
1. 주어진 점의 꼭지점을 사용하여 가능한 모든 삼각형을 반복합니다.
2. 각 삼각형에 대해 나머지 점이 삼각형 내부에 있는지 확인합니다.
3. 삼각형 내부에 점이 없으면 발견된 첫 번째 삼각형의 좌표를 반환합니다.
#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));
산출
[[0 0] [0 2] [1 1]]
시간 복잡도: O(n^4) 여기서 n은 포인트 수입니다. 이는 n이 3을 선택한 가능한 모든 삼각형을 반복한 다음 나머지 각 점이 O(n)인 삼각형 내부에 있는지 확인해야 하기 때문입니다.
공간 복잡도: O(1) 한 번에 몇 개의 변수만 저장하기 때문입니다.
퀴즈 만들기