408038: GYM102966 B Baking Lucky Cakes

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Baking Lucky Cakestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExamplesInput
2
1 1
-1 -1
Output
0
Input
3
1 1
-1 -1
1 -1
Output
1
Input
7
0 0
1 0
1 1
2 2
2 3
3 3
4 4
Output
2

加入题单

上一题 下一题 算法标签: