View as PDF

Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Ozi's new friend Yusuf is developing an innovative game about mining in which everything is pixelated. He is creating different kinds of textures. However, he has had problems while creating a specific kind of texture and wanted Ozi's help to create this texture.

To create this texture, Yusuf first needs to draw random individual black points on a white plane. Then, he needs to create a triangle by choosing three black points such that there are no black points inside the newly-created triangle. He already created a texture that has random black points in it, but he is having trouble coming up with an algorithm to find a triangle meeting his requirements consistently. He shares this texture with Ozi and wants him to write a program that finds a nondegenerate triangle with no black points in it.

Ozi doesn't have the time nor the energy to help Yusuf due to all his schoolwork, can you help him write that program?

Note that triangles should not have points inside them, points on the boundary wouldn't matter since they aren't inside.


The first line contains a single integer \(n\).

Each of the next \(n\) lines contains the coordinates of a black point \(x_i\) and \(y_i\).

  • \(3 \leq n \leq  10^5\)
  • \(-1000 \leq x_i, y_i \leq 1000\)

It is guaranteed that no two points are located in the same position, and there does not exist a line such that all points lie on that line.


Print the indices (their order according to the input) of three points in a single line. The corresponding points should form a triangle, and there shouldn't be any points located inside this triangle.

If there are multiple possible answers, you may print any of them. Such a triangle always exists.



1 2
2 3
3 2


1 2 3


1 2
2 3
3 4
4 5
2 1


1 2 5


In the first input, the only valid answer is the triangle composed of the given 3 points. Those indices can be printed in any order.

In the second input, there are more than one valid answer. ({1, 2, 5}, {1, 3, 5}, {1, 4, 5}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}) Note that any other other triangle composed with those points would be degenerate.