分类讨论凸包顶点数量 $m$：

• $m\le 2$：所有点共线，一定合法。

• $m\ge 4$：不合法。

• $m=3$：如果存在顶点以外的两个点 $P_i,P_j$ 满足直线 $P_iP_j$ 不经过任何一个凸包顶点，则选择这两个点和直线一侧的两个凸包顶点就是凸四边形。继续讨论：

  • 如果凸包内所有点共线：合法。

  • 如果不共线，设三个不共线的点是 $O,G,H$。不妨设 $OG$ 和 $OH$ 分别经过了 $A$ 和 $B$，则不可能 $G$ 在 $OA$ 上且 $H$ 在 $OB$ 上，否则 $ABHG$ 是凸四边形；都不在也不行。不妨设 $G$ 在 $OA$ 上，$H$ 在 $BO$ 的延长线上，则 $C,H,G$ 必须共线，否则 $BCHG$ 或者 $CAGH$ 是凸四边形。再这个基础上加任何一个点都会不合法，因此唯一的情况如下图所示：

    

除上图的情况以外，合法的集合可以看成选择一个点 $O$ 和三个方向，满足这三个方向不在同一个半平面（可以刚好差 $180^\circ$），选一个方向的所有点和另外两个方向的至多一个点。枚举点 $O$ 和选择所有点的方向 $v$，则另外两个方向一定是在 $v$ 两侧分别和 $v$ 的距离尽可能远，可以极角排序后双指针，时间复杂度 $O(N^2\log N)$。

上图的情况可以枚举 $O,G,H$，检查三条延长线上是否都有点，判断延长线上是否有点可以预处理，时间复杂度 $O(N^3)$。