Given point A and a new tree, find the smallest pair (B, C) so triangle ABC is counterclockwise, contains the new tree strictly, and contains no other old tree.
Medium6GeometryBrute forceNo attempts yetTime limit0.2sMemory limit1024 MBA new tree was planted in the city park and the gardener wants to protect it. He picks three of the old trees, stretches a band around them, and the triangle enclosed by the band becomes the protected area. The new tree has to stand strictly inside that triangle, and no other tree may stand inside it or on its border.
The gardener has already picked one old tree, the one numbered A. Find the other two.
The old trees are numbered 1 to N. A pair of numbers (B,C) is valid when all of the following hold:
The first line has two integers N and A (3≤N≤300, 1≤A≤N): the number of old trees and the number of the tree the gardener has already picked.
The second line has two integers x and y, the coordinates of the new tree.
Each of the next N lines has two integers x and y (−106≤x,y≤106), the coordinates of one old tree, given in order of the tree numbers. The N+1 points are pairwise distinct.
Print B and C on one line, separated by a single space, so that A, B, C in that order form a valid protected area.
If several pairs are valid, print the smallest one: compare B first, and compare C only when the two values of B are equal. If no pair is valid, print 0 0.