四角形が凸であるということは、 \(4\) 点の凸包 ( https://ja.wikipedia.org/wiki/%E5%87%B8%E5%8C%85 ) が四角形と一致することと同値です。

よって \(4\) 点の凸包を求め、頂点数が \(4\) であるかを確認すればよいです。 \(N\) 点の凸包は \(O \left( N \log N \right)\) で求めることができるので、これでもこの問題を解くことができます。