题目大意
给定二维平面上的 \(n\) 个点，每个点标有左括号或右括号。
需要选出一组点构成凸多边形，使得从任意左括号点出发按凸多边形顺序得到的括号序列均为合法括号序列。
保证不存在三点共线，\(n \le 2000\) 。
题解
这题很简单吧，比 E 简单多了。
可能因为大家见到计几就害怕，所以都没开这个题。
首先肯定的是，合法凸包的节点数一定是偶数，如果一个大小为 \(k\) 的凸包是合法的话，那么它的子集里肯定存在一个大小为 \(4\) 的凸包是合法的，因为每次增加两个点只会带来更多的约束。
所以我们只需要找大小为 \(4\) 的凸包。
考虑构造 \(()()\) 和 \((())\) 。
对于第一种情况，从任意 \((\) 出发的回路都是合法的。
对于第二种情况，会存在 \(())(\) 这种回路，所以是不合法的。
现在只有第一种情况，依旧难做，考虑继续化简，那这个图形有什么性质呢。
考虑将同色点连接线段，你会发现如果有异色线段相交，则存在以上图形。
因为题面里说不存在三点共线，所以不存在反例。
因为 \(n\) 很小，所以我们可以先把点按照 \(x\) 排序，维护左括号点集的凸包，遇到右括号点就枚举以当前点为端点所有可行边，判断和凸包有没有交点就可以了。而且实际上我们并不需要维护凸包，凸包的构建是 \(O(n)\) 的，所以每次有新点加入时重构就可以了。
考虑怎么判断凸包和线段有没有交点，算出右括号线段的斜率，在面朝当前右括号点的凸壳上二分就可以了，这样的实现是 \(O(n^2logn)\) 的。
没错，这就可以通过本题了（
那我们怎么优化到 \(O(nlogn)\) 呢，
有这样一个定理：
- 如果红蓝两个点集存在相交的线段，那么必然存在一对相交的线段，其中一条属于某个点集的 Delaunay 三角剖分的边。
具体为啥我也不会证，总之三角剖分后，我们的右括号边枚举就可以被优化到线性，然后搞一个平衡树维护动态凸包就可以了。