AT_arc173_b [ARC173B] Make Many Triangles
Description
[problemUrl]: https://atcoder.jp/contests/arc173/tasks/arc173_b
二次元平面上に相異なる $ N $ 個の点があります。 $ i $ 番目の点の座標は $ (x_i,y_i) $ です。
これらの点のいずれかを頂点とする(非退化な)三角形をたくさん作りたいです。ただし、同じ点を複数の三角形の頂点として用いることはできません。
最大で何個の三角形が作れるか求めてください。
非退化な三角形とは 非退化な三角形とは、 $ 3 $ つの頂点が同一直線上に並ばない三角形のことを指します。
Input Format
入力は以下の形式で標準入力から与えられる。
> $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_{N} $ $ y_{N} $
Output Format
答えを出力せよ。
Explanation/Hint
### 制約
- $ 3\ \leq\ N\ \leq\ 300 $
- $ -10^9\ \leq\ x_i,y_i\ \leq\ 10^9 $
- $ i\ \neq\ j $ ならば $ (x_i,y_i)\ \neq\ (x_j,y_j) $
- 入力される値はすべて整数
### Sample Explanation 1
例えば $ 1,3,6 $ 番目の点からなる三角形と $ 2,4,5 $ 番目の点からなる三角形を考えると、三角形を $ 2 $ つ作ることができます。 同じ点を複数の三角形の頂点として用いることはできませんが、三角形が共通部分を持っても構いません。