DMPG '19 B5 - Triangles

View as PDF

Submit solution

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

Problem type

There are N points labelled from 1 to N. The point labelled i is located at (x_i, y_i). These N points are coloured such that the point labelled i has colour c_i. There are only two colours, red or blue. If c_i is 1, the point is red and if c_i is 2, the point is blue. It is guaranteed that no two have the same coordinates. Can you choose 3 of the N points such that none of the other N-3 points lie within the interior of the (possibly degenerate) triangle formed by the 3 points and such that the colours of the 3 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 3 collinear points will guarantee no other points in its interior.


1 \le c_i \le 2 for all 1 \le i \le N
1 \le x_i, y_i \le 10^6 for all 1 \le i \le N
3 \le N \le 200\,000

Input Specification

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

Output Specification

If it is not possible to find 3 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

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

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

Sample Output 2

1 2 4


There are no comments at the moment.