// C/C++ program to find triangle with no point inside #include    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 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> 

#include    #include  #include  using namespace std; // Function to calculate the area of a triangle given its three vertices double area(double x1 double y1 double x2 double y2 double x3 double y3) {  return 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) 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 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 vector<vector<double>> noPointInsideTriangle(vector<vector<double>> 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) {  bool inside = false;  for (int l = 0; l < points.size(); ++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) {  vector<vector<double>> result = {points[i] points[j] points[k]};  return result;  }  }  }  }  return vector<vector<double>>(); // Return an empty vector if no such set of points is found } int main() {  vector<vector<double>> points = {{0 0} {0 2} {2 0} {2 2} {1 1}};  vector<vector<double>> result = noPointInsideTriangle(points);    if (!result.empty()) {  cout << 'Points that do not form a triangle with any other point inside:' << endl;  for (const auto& point : result) {  cout << '(' << point[0] << ' ' << point[1] << ')' << endl;  }  } else {  cout << 'No such set of points found.' << endl;  }  return 0; } 

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));