\(P_{i}, Q_{j}\) を結ぶ直線で平面を分割します。 このとき、ある面に含まれる \(P\) の数と \(Q\) の数が等しければ、\(N\) の小さい問題に帰着できます。 \((i, j)\) の組をひとつ見つければ、再帰的に解けます。

このような直線は問題の条件下(同一直線上に異なる \(3\) 点が存在することはない下)で必ず存在します。 また、 \(P_{i}\) が凸包に含まれるとき、この \(i\) を用いて、 \((i, j)\) が上記の条件を満たす組になるような \(j\) が存在します。そのような \(i\) を \(1\) つ固定し(実装上では、 \(x\) 座標が最も小さい値にすれば良いです)、\(j\) を全探索することで、 \(O(N^{2})\) で組 \((i, j)\) を見つけられます。

よって、この問題は全体で \(O(N^{3})\) で解けます。

https://atcoder.jp/contests/abc373/submissions/58243100

この解説は maspy さんによる解説 に比べて計算量が悪いですが、一から実装するならこちらはかなり楽だと思っています。