There are N points on a plane, numbered from 0 to N – 1. The coordinates of the K-th point are (X[K], Y[K]). Find any triangle with vertices at three of the given points, such that no other point lies inside this triangle (and no other points, except vertices, on the boundary of the triangle). The triangle must have a positive area.
Write a function:
def solution(X, Y)that, given two arrays X and Y consisting of N integers each, representing points on the plane, returns an array B consisting of exactly three integers, such that the points with indices B[0], B[1], and B[2] form an empty triangle.
If there is no such triplet, return an empty array instead.
Examples:
1. Given X = [1, 4, 3, 2, 3] and Y = [4, 3, 1, 1, 2], there are N = 5 points on the plane as in the image below.
The function could return [0, 1, 4], since points 0, 1, and 4 form an empty triangle. Answer [0, 1, 2] would be incorrect, since triangle 0, 1, 2 contains point 4 inside. Answer [0, 1, 3] would be incorrect, since triangle 0, 1, 3 contains point 4 on the boundary. Answer [1, 3, 4] would be incorrect, since 1, 3, 4 do not form a triangle with positive area. Answer [4, 2, 3] would be considered correct, since points 2, 3 and 4 also form an empty triangle.
This Microsoft OA problem asks you to pick any three given points that form a non-degenerate triangle with no other points inside or on its boundary. The core challenge is verifying positive area and emptiness with respect to all other points, while handling collinear cases and the possibility that no valid triangle exists. Depending on the constraints, common approaches involve geometry checks with orientation tests, convex hull ideas, or constructive candidate selection to avoid brute-force enumeration.
