在自己写出了 $O(n^3)$ 做法之后，看到 CF 的比赛公告下有人回复存在 $O(n^2)$ 或 $O(n^2\log n)$ 的做法，貌似需要维护凸包，不过本蒟蒻没有看懂，求大佬指点，谢谢qwq