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.
这道 Microsoft OA 题要求在平面上的 N 个点中找出任意三个点，组成一个“空三角形”——不仅三点不能共线，而且三角形内部和边界上都不能再包含其他点。关键在于判断三点是否形成正面积三角形，并检查所有其他点相对三角形三条边的方向关系；更高效的做法通常会利用凸包、旋转卡壳或随机 / 构造性选点来尽快找到一个满足条件的三元组。题目强调返回任意合法答案即可，因此不需要枚举所有三角形，但必须严格处理共线、边界点和“没有解”返回空数组的情况。
