Choosing Points

Time limit2sMemory limit128 MB

Summary
Given up to 1000 planar points, find the largest subset where every line through two chosen points also passes through a third chosen point, or report -1 if impossible.
Level

Hard9 of 10

Topics
Geometry, Combinatorics, Brute force, Math
Solved
No attempts yet

Problem

There are N distinct points on a two-dimensional plane. Choose some of the points so that all of the following conditions hold.

  1. At least three points must be chosen.
  2. For any two chosen points, consider the line passing through them. That line must contain at least one other chosen point besides those two.
  3. The number of chosen points must be as large as possible.

Given the coordinates of all points, find the maximum number of points that can be chosen while satisfying the conditions.

Input

The first line contains the number of points N (3 <= N <= 1,000).

Each of the next N lines contains two integers, the x-coordinate and y-coordinate of one point. The absolute value of every coordinate is at most 20,000. All given points are distinct.

Output

Print the maximum number of points that can be chosen while satisfying the conditions. If no valid choice exists, print -1.

Examples1

  1. Example 1

    Input
    3
0 0
1 0
0 1
    Expected output
    -1