Problem Description

AtCoder Transportation Company has $ N $ factories.

In the year 217X, the company is facing a major issue: there are no roads connecting the factories.

The CEO of the transportation company exclaims, "This is a big problem!! We need to fix this immediately!!"

Therefore, they have decided to plan the construction immediately.

Since the company deals with transportation, they need to quickly transport products from rural areas to cities and from cities to rural areas. Therefore, building company-exclusive roads will allow them to handle many orders.

However, the roads must be built under the following conditions:

• To increase the speed limit for transportation trucks, the roads must be straight.
• Intersections will significantly increase costs, so roads must not intersect except at factories.
• With all the exclusive roads having a high speed limit, they want to build as many roads as possible to quickly transport goods to the target factories.
• Roads connect between factories.

However, the company does not know how to derive the optimal solution.

Therefore, the company has asked you, an excellent programmer, to find the optimal solution. Determine the maximum number of roads that can be built.

Please adhere to the conditions stated in the problem.

Note: The year 217X in the problem is considered to be a time beyond spacetime. You can consider this time to be the present.

Input Format

Input is given from standard input in the following format:

$ N $ $ x_1 $ $ y_1 $ $ : $ $ : $ $ x_N $ $ y_N $

• The first line contains the total number of factories $ N $.
• From the second line to the $ N+1 $th line, the coordinates $ (x_i, y_i) $ of factory $ i $ are given.

Output Format

Output should follow the standard output format:

• Output the maximum number of roads that can be built in one line.

Sample Input and Output

Sample Input #1

4
0 0
1 1
0 1
1 0

Sample Output #1

5

Sample Input #2

4
0 0
1 2
2 0
1 1

Sample Output #2

6

Notes/Hints

Constraints

• $1 \leq N \leq 2,000$
• $0 \leq x_i, y_i \leq 1,000,000,000$
• No three factories are collinear.

Subtasks

Subtask $ 1 $ \[ $ 14 $ points \]

• Satisfies $1 \leq N \leq 4$.

Subtask $ 2 $ \[ $ 50 $ points \]

• Satisfies $1 \leq N \leq 100$.

Subtask $ 3 $ \[ $ 36 $ points \]

• No additional constraints.

Sample Explanation 1

Connecting points {$ (1,2), (1,3), (2,3), (1,4), (2,4) $} allows building 5 roads that meet the conditions.

Sample Explanation 2

In this case, all edges can be connected.

见题面 Input 部分

见题面 Output 部分