Don't make triangle

解説

まずは、$3$ 点が与えられたときに条件を満たすような直線が存在するかどうかを判定することを考えてみましょう。各点の座標を $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ で表すことにします。 このとき、与えられた $3$ 点を通るような直線が存在するためには、点 $1,2$ を通る直線と点 $1,3$ を通る直線の傾きが等しくなること、つまり $\displaystyle\frac{y_2-y_1}{x_2-x_1} = \frac{y_3-y_1}{x_3-x_1}$ が成り立てば良いです。この判定は分数を最大公約数を利用して通分することで簡単にできます。 また、直線が存在するとき、その直線が条件を満たすためには与えられた $3$ 点以外の全ての点で、その座標を $(x_b,y_b)$ としたときに$\displaystyle\frac{y_2-y_1}{x_2-x_1} = \frac{y_b-y_1}{x_b-x_1}$ を満たさなければ良いです。

しかし、これらをそのまま愚直に実装すると、$3$ 点の列挙に $O(N^3)$ 、列挙した $3$ 点のみを通る直線が存在するかどうかの判定に $O(N)$ かかるので、全体として $O(N^4)$ 程度になってしまいます。そのため、高速化を考えることにします。

ここで、$1$ 点を固定(座標を $(x_p,y_p)$ とする)して考えることにします。このとき、この点を通るような直線は必ずこの点を通ることから、残りの $N-1$ 個の点をこの直線の傾きで分類できます。その中で、傾きの等しい点がちょうど $2$ つあれば、その傾きを $a$ として直線　$(y-y_p)=a(x-x_p)$ は条件を満たします。よって、この傾き $a$ を $N$ 個それぞれの点を固定したときに数えあげることで答えが求まります。ただし、同じ直線を $3$ 回重複して数えることになるので、 数え上げた $a$ の個数を $3$ で割ることに注意してください。また、傾きを求める際にx軸やy軸に平行になるような直線は、例外処理する必要があります。

計算量は、固定する点の列挙に $O(N)$ 、残りの $N-1$ 個の点を傾きで分類するのは傾きを分数で表し、分母と分子の絶対値の最大公約数で割って通分することで傾きをkey、個数をvalueとした平衡二分木を作ることができるので $O(N\log(N)\log(\max(x_i,y_i)))$ となるので、全体として $O(N^2\log{N}\log(\max(x_i,y_i)))$ となり、本制約下において十分高速です。

追記

pythonの場合、dictはランダムアクセスを利用する関係上若干実行時間がギリギリ怪しいです。(制約が比較的小さいのもこれが原因だったりします。)