Triangle

Time limit3sMemory limit128 MB

Summary
Given up to 300 planar points, find three non-collinear points forming a triangle that contains the maximum number of the given points, counting boundary points.
Level

Hard8 of 10

Topics
Geometry, Brute force, Combinatorics
Solved
No attempts yet

Problem

There are N points on a plane.

Choose three of the given points that are not collinear to form a triangle. If a triangle contains as many of the given points as possible, it is called a super triangle. Points on an edge or at a vertex of the triangle are also counted as contained.

Find three given points that form a super triangle.

Input

The first line contains N (3 ≤ N ≤ 300), the number of points.

Each of the next N lines contains the coordinates xi and yi of one point.

The input always contains at least one set of three points that are not collinear.

Output

On the first line, print the number of given points contained in a super triangle.

On the second line, print the three point numbers that form that triangle, in any order.

If there is more than one valid answer, print any one of them.

Examples3

  1. Example 1

    Input
    6
1 3
2 3
2 1
3 1
3 2
4 4
    Expected output
    5
1 4 6

  2. Example 2

    Input
    9
1 1
2 2
3 3
2 1
3 2
3 1
4 2
4 1
5 1
    Expected output
    9
1 9 3

  3. Example 3

    Input
    13
1 3
2 4
3 1
4 1
4 2
4 3
4 4
4 5
5 1
5 2
6 1
6 5
7 3
    Expected output
    9
3 11 8