408038: GYM102966 B Baking Lucky Cakes

Alan is a pastry chief owning a famous pastry shop downtown. He just received an order to prepare a lucky cake of diameter $$$10^9$$$ from a customer. If we represent a lucky cake as a circle centered in the origin, there are $$$n$$$ lucky points $$$(x,y)$$$, where each point can contain at most one chocolate chip, and a chocolate chip can only be placed in a lucky point.

Each chip can be one of $$$n$$$ different colors, and Alan has $$$n$$$ chips available of each color. A cake is called lucky if all the chips of the same color can be used as vertices of a non-degenerate triangle. In other words, for all the colors of chocolate chips used in a lucky cake, we can draw a non-degenerate triangle with all the chocolate chips of that color. The customer requires that Alan prepares a lucky cake with the maximum possible number of colors.

Help Alan to find the maximum number of colors that he can use to complete the order.

The first line contain in integer $$$n$$$ ($$$1 \leq n \leq 1000$$$).

The following $$$n$$$ lines contain the lucky points $$$(x,y)$$$ ($$$|x_i|, |y_i| \leq 10^5$$$).

It is guaranteed that all the given points are pairwise distinct.

Print the maximum number of colors that can be used in a lucky cake.

2
1 1
-1 -1

0

3
1 1
-1 -1
1 -1

1

7
0 0
1 0
1 1
2 2
2 3
3 3
4 4

2