## DMPG '19 B5 - Triangles

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

There are points labelled from to . The point labelled is located at . These points are coloured such that the point labelled has colour . There are only two colours, red or blue. If is , the point is red and if is , the point is blue. It is guaranteed that no two have the same coordinates. Can you choose of the points such that none of the other points lie within the interior of the (possibly degenerate) triangle formed by the points and such that the colours of the points are not all the same? A point on the boundary of the triangle is not considered within the interior of the triangle for this problem. In particular, choosing collinear points will guarantee no other points in its interior.

for all
for all

#### Input Specification

The first line contains a single integer, .
The next lines each contain three space-separated integers, , , and .

#### Output Specification

If it is not possible to find such points, output -1. Otherwise, print three space-separated integers i j k on a single line representing the three points chosen. If there are multiple possibilities, any triplet will be accepted. The triplet does not need to be written in any particular order.

#### Sample Input 1

6
1 1 1
7 7 2
1 7 1
7 1 1
2 3 1
6 5 1

#### Sample Output 1

2 3 5

#### Sample Input 2

4
1 1 1
1 2 2
1 3 1
1 4 1

#### Sample Output 2

1 2 4