New Tree
Time limit0.2sMemory limit1024 MB
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.
- Level
Medium6 of 10
- Topics
- Geometry, Brute force
- Solved
- No attempts yet
Problem
A 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 . Find the other two.
The old trees are numbered to . A pair of numbers is valid when all of the following hold:
- and are different from each other and both are different from .
- Walking the old trees , , in that order turns counterclockwise, so the three points are not collinear.
- The new tree lies strictly inside triangle , not on one of its sides.
- No old tree other than , and lies inside triangle or on one of its three sides.
Input
The first line has two integers and (, ): the number of old trees and the number of the tree the gardener has already picked.
The second line has two integers and , the coordinates of the new tree.
Each of the next lines has two integers and (), the coordinates of one old tree, given in order of the tree numbers. The points are pairwise distinct.
Output
Print and on one line, separated by a single space, so that , , in that order form a valid protected area.
If several pairs are valid, print the smallest one: compare first, and compare only when the two values of are equal. If no pair is valid, print 0 0.