$O(N^2 \log N)$ での解法を紹介します。 $3$ 点を選ぶ方法で、選んだ $3$ 点を線分で結んだ図形が三角形にならない必要十分条件は「選んだ $3$ 点が一直線上にあること」です。
選んだ $3$ 点が一直線上にあるような選び方を求める方法を考えましょう。選んだ $2$ 点を結んでできる直線は $O(N^2)$ 通りあります。よって、考慮するべき直線は $O(N^2)$ 通りとなります。この全てについてその直線上の点の数を求めればよいです。

初めに、選んだ $2$ 点を結んでできる直線を求めることを考えましょう。これは $2$ 点を $\left(x_1,y_1 \right),\left(x_2,y_2 \right)$ として $\left(y_2-y_1\right)x+\left(x_1-x_2\right)y+\left(x_2-x_1\right)y_1-\left(y_2-y_1\right)x_1 =0$ として表すことができるので、 $O(1)$ で求まります。直線は $x,y$ の係数と定数からなるtupleなどを用いて管理するとします。直線 $ax+by=c$ を $\left( a,b,c \right)$ として管理する際、 $\gcd (a,b,c)=1$ かつ $a \geq 0$ を満たすように $a,b,c$ に同じ数をかけたり割る操作をするとよいです。
次にmapを用いて点 $i$ と点 $j$ を結んでできる直線の登場回数を管理します。 $i < j$ として $O(N^2)$ で調べた時、mapのtupleに対応する値はその直線上の点の数を $v$ として ${}_v C_2$ です。

直線上の点の数を $v$ としたとき、 $3$ 点がその直線上にあるような選び方は ${}_v C_3$ 通りです。よって、 ${}_v C_2$ から $v$ を求める逆配列をmapなどで作ればよいです。
最後に、 $N$ 個の中から $3$ 点を選ぶのは ${}_N C_3$ 通りなので、求めた値を ${}_N C_3$ から引けば答えが求まります。
mapを使用する関係上 $\log$ がつき計算量は$O(N^2 \log N)$ となります。

実装例(C++)