$O(n\log n)$ 做法

1. 问题转化

把左括号点称为 A 类点，右括号点称为 B 类点。

根据题解转换，原问题等价于：是否存在一条 A-A 线段和一条 B-B 线段严格相交。

如果存在这样的两条线段，那么它们的四个端点构成一个颜色交替的凸四边形，也就是一个合法答案。

2. 好点与关键结构

定义一个点为好点，表示它参与至少一个答案。

如果 $p$ 是 A 类点，那么 $p$ 是好点，当且仅当存在 $q\in A$ 和 $x,y\in B$，使得：

$$ pq\cap xy\ne\varnothing $$

其中 $pq$ 和 $xy$ 是严格相交的两条线段。

如果 $p$ 是 B 类点，则定义完全对称。

关键结论：如果存在答案，那么要么所有 A 类点都是好点，要么所有 B 类点都是好点。

下面证明这个结论。

假设已经存在一组答案：

$$ a_1,a_2\in A,\qquad b_1,b_2\in B $$

并且：

$$ a_1a_2\cap b_1b_2\ne\varnothing $$

这四个点构成一个颜色交替的凸四边形。

令两条对角线的交点为 $O$。通过仿射变换，可以把两条对角线分别变成横轴和纵轴，并把交点 $O$ 变成原点。

于是可以认为：

$$ a_1=(-\alpha,0),\qquad a_2=(\beta,0) $$

$$ b_1=(0,\gamma),\qquad b_2=(0,-\delta) $$

其中 $\alpha,\beta,\gamma,\delta>0$。

注意这里不要求四个端点关于原点对称，只需要两条对角线分别在横轴和纵轴上。

考虑一个额外的 A 类点 $a$。

如果 $a$ 不是好点，那么特别地，$aa_1$ 和 $aa_2$ 都不能与固定线段 $b_1b_2$ 严格相交。

这会限制 $a$ 只能落在两个外锥区域中：

1. 以 $b_1$ 为顶点，由射线 $b_1a_1$、$b_1a_2$ 向外延伸形成的上方外锥；
2. 以 $b_2$ 为顶点，由射线 $b_2a_1$、$b_2a_2$ 向外延伸形成的下方外锥。

直观理解就是：如果一个 A 点没有躲到 $b_1$ 上方或者 $b_2$ 下方，那么它连向 $a_1$ 或 $a_2$ 的线段一定会穿过 $b_1b_2$，于是它就是好点。

所以，坏 A 点只能落在 $b_1$ 外锥或 $b_2$ 外锥中。

同理，如果一个 B 类点 $b$ 不是好点，那么 $bb_1$ 和 $bb_2$ 都不能与固定线段 $a_1a_2$ 严格相交。

因此坏 B 点只能落在两个外锥区域中：

1. 以 $a_1$ 为顶点，由射线 $a_1b_1$、$a_1b_2$ 向外延伸形成的左侧外锥；
2. 以 $a_2$ 为顶点，由射线 $a_2b_1$、$a_2b_2$ 向外延伸形成的右侧外锥。

也就是说，坏 B 点只能落在 $a_1$ 外锥或 $a_2$ 外锥中。

现在假设同时存在坏 A 点 $a$ 和坏 B 点 $b$。

根据上面的外锥分类，一共有四种情况：

每一种情况都会产生一对新的严格相交的同色线段，从而产生一个答案，矛盾。

因此坏 A 点和坏 B 点不能同时存在。

于是：

• 如果存在坏 A 点，那么所有 B 点都是好点；
• 如果存在坏 B 点，那么所有 A 点都是好点；
• 如果两边都没有坏点，那么所有点都是好点。

所以关键结论成立。

根据这个结论，全局只需要检查两个点：

1. 任取一个 A 类点 $a$，检查是否存在包含 $a$ 的答案；
2. 如果失败，任取一个 B 类点 $b$，检查是否存在包含 $b$ 的答案；
3. 如果两次都失败，则无解。

因为如果有解，那么至少有一种颜色的所有点都是好点，所以任取一个 A 点和任取一个 B 点，其中至少一个一定是好点。

核心问题变成固定点检查，记为 check(p)。

3. 固定点检查与射影变换

假设固定点 $p$ 是 A 类点。

令：

• $C$ 表示与 $p$ 同色的点集，也就是 A 类点；
• $S$ 表示与 $p$ 异色的点集，也就是 B 类点。

我们需要判断是否存在：

$$ q\in C,\qquad x,y\in S $$

使得：

$$ pq\cap xy\ne\varnothing $$

其中 $q\ne p$。

如果固定点 $p$ 是 B 类点，则完全对称。

首先把 $p$ 平移到原点。

然后选择一条经过 $p$ 的直线作为新的 $x$ 轴，并保证没有其他输入点落在这条新的 $x$ 轴上。

之后所有点的坐标都用这个以 $p$ 为原点的新坐标系表示，仍然记为 $(x,y)$。

因为没有其他点落在新的 $x$ 轴上，所以对所有 $r\ne p$ 都有 $y_r\ne 0$。

对每个点 $r=(x_r,y_r)$，做射影变换：

$$ r'=\Phi(r)=\left(\frac{x_r}{y_r},\frac1{y_r}\right) $$

记变换后的点为：

$$ r'=(X_r,Y_r) $$

也就是说：

$$ X_r=\frac{x_r}{y_r},\qquad Y_r=\frac1{y_r} $$

后文中：

• $x_r,y_r$ 表示射影变换前、以 $p$ 为原点的新坐标；
• $X_r,Y_r$ 表示射影变换后的坐标；
• $r'$ 表示点 $r$ 经过射影变换后的点。

例如，点 $u,d,q$ 经过变换后分别写作 $u',d',q'$，它们的坐标分别是：

$$ u'=(X_u,Y_u),\qquad d'=(X_d,Y_d),\qquad q'=(X_q,Y_q) $$

所有形如 $X_u,Y_u,X_d,Y_d$ 的记号，都表示变换后的坐标，不是原来的坐标。

这个变换的关键性质是：

经过固定点 $p$ 的直线，会变成变换平面中的竖直直线。

因为经过 $p$ 的一条射线可以写成 $(tx,ty)$，变换后有：

$$ X=\frac{tx}{ty}=\frac{x}{y} $$

所以 $X$ 是常数。

因此，原平面中的线段 $pq$ 会变成变换平面中的一条竖直射线。

如果 $q$ 满足 $y_q>0$，那么 $Y_q>0$，从 $p$ 走到 $q$ 对应于在变换平面中沿竖直线 $X=X_q$ 从 $Y=+\infty$ 下降到 $Y_q$。

如果在下降过程中先遇到某个由异色点生成的阻挡物，那么原平面中 $pq$ 就与某条异色线段相交。

如果 $q$ 满足 $y_q<0$，则完全对称，对应于从 $Y=-\infty$ 上升到 $Y_q$。

需要注意的是，射影变换会把新的 $x$ 轴，也就是 $y=0$，送到无穷远。

因此，它不会把所有普通线段都变成普通有限线段：

• 如果一条线段的两个端点都在 $y>0$，变换后仍是一条普通有限线段；
• 如果一条线段的两个端点都在 $y<0$，变换后仍是一条普通有限线段；
• 如果一条线段跨过 $y=0$，变换后会分裂成两条射线，分别属于 $Y>0$ 和 $Y<0$ 两侧。

这不会影响固定点检查。

因为我们只关心 $pq$ 与异色线段 $xy$ 的交点。线段 $pq$ 与 $y=0$ 的交点只有 $p$，而异色线段 $xy$ 不经过 $p$。所以真正的交点不会在被送到无穷远的直线上。

因此，只要正确地把跨越 $y=0$ 的异色线段处理成射线，相交关系就可以正确判断。

4. 上半平面的检查

先处理所有满足 $Y_q>0$ 的同色查询点 $q$。

把异色点 $S$ 在变换后分成两类：

$$ U={s\in S\mid Y_s>0} $$

$$ D={s\in S\mid Y_s<0} $$

由于 $Y_s=1/y_s$，所以 $Y_s>0$ 等价于变换前的 $y_s>0$。

对于上半平面的查询点，可能挡住它的异色线段只有两类：

1. 两端都在 $U$ 的线段；
2. 一端在 $U$，一端在 $D$ 的线段，在上半平面对应的射线。

两端都在 $D$ 的线段完全位于下半平面，不可能挡住从 $Y=+\infty$ 走向 $Y_q>0$ 的竖直射线。

$U-U$ 线段

考虑两个异色点 $u,v\in U$。

它们在变换前都满足 $y>0$，所以原线段 $uv$ 不会穿过 $y=0$。

经过射影变换后，线段 $uv$ 仍然是一条普通有限线段，连接变换后的两个点：

$$ u'=(X_u,Y_u),\qquad v'=(X_v,Y_v) $$

所有 $U-U$ 线段的最高部分，正好是点集 $U'={u'\mid u\in U}$ 的上凸壳。

原因是任意 $U-U$ 线段变换后都包含在 $\operatorname{conv}(U')$ 中，而从 $Y=+\infty$ 往下看，最先遇到的只可能是凸包上边界。

所以第一类阻挡物只需要维护 $U'$ 的上凸壳。

对每个查询点 $q$，如果 $X_q$ 落在上凸壳的横坐标范围内，就二分找到对应凸壳边，并计算该边在 $X_q$ 处的高度。

如果该高度大于 $Y_q$，就找到答案。

这一部分复杂度为 $O(n\log n)$。

$U-D$ 线段产生的射线

考虑异色点 $u\in U$ 和 $d\in D$。

它们经过射影变换后分别为：

$$ u'=(X_u,Y_u),\qquad d'=(X_d,Y_d) $$

原平面中的线段 $ud$ 跨过新的 $x$ 轴，也就是 $y=0$。

经过射影变换后，它在上半平面 $Y>0$ 这一侧对应为一条从 $u'$ 出发的射线：

$$ u' + \lambda (u'-d'),\qquad \lambda\ge 0 $$

也就是从 $u'$ 朝远离 $d'$ 的方向延伸。

这条射线所在直线就是经过 $u'$ 和 $d'$ 的直线，其斜率为：

$$ k(u,d)=\frac{Y_u-Y_d}{X_u-X_d} $$

这里的 $X_u,Y_u,X_d,Y_d$ 都是变换后的坐标。

如果 $X_d0$，所以这条射线向右延伸，有效区间为 $X\ge X_u$。

它在横坐标 $X$ 处的高度是：

$$ Y_u+(X-X_u)\cdot \frac{Y_u-Y_d}{X_u-X_d} $$

对于固定的 $u$，当 $X\ge X_u$ 时，有 $X-X_u\ge 0$。

所以在所有满足 $X_d< X_u$ 的 $ d \in D $ 中，只需要保留斜率最大的那个：

$$ d_R(u)=\arg\max_{d\in D,\ X_d< X_u}\frac{Y_u-Y_d}{X_u-X_d} $$

这样得到的射线在所有 $X\ge X_u$ 上都不低于其他从同一个 $u$ 出发的向右射线。

如果 $X_d>X_u$，那么射线向左延伸，有效区间为 $X\le X_u$。

此时 $X-X_u\le 0$，所以对于固定的 $u$，需要保留斜率最小的那个：

$$ d_L(u)=\arg\min_{d\in D,\ X_d>X_u}\frac{Y_u-Y_d}{X_u-X_d} $$

这样得到的射线在所有 $X\le X_u$ 上都不低于其他从同一个 $u$ 出发的向左射线。

因此，虽然 $U-D$ 线段总数可能是二次的，但真正需要保留的射线数量是线性的：每个 $u$ 最多贡献一条向右射线和一条向左射线。

如何求最优射线并查询

先求所有 $d_R(u)$。

把 $U'$ 和 $D'$ 都按照变换后的横坐标 $X$ 从小到大排序，然后从左到右扫描。

当扫描到某个 $u'$ 时，所有满足 $X_d< X_{u}$

的 $D'$ 点已经被加入数据结构。

此时要在当前已经加入的 $D'$ 点中找一个点 $d'$，使得从 $d'$ 连到 $u'$ 的直线斜率最大。

这个最优点一定在当前 $D'$ 点集的下凸壳上。

由于 $D'$ 点按照 $X$ 单调加入，可以用单调栈维护下凸壳。每次查询 $u'$ 时，在下凸壳上二分找斜率最大的切点即可。

因此所有 $d_R(u)$ 可以在 $O(n\log n)$ 时间内求出。

对于 $d_L(u)$，完全对称处理。可以把所有变换后的点做镜像 $X\mapsto -X$，这样原来位于右侧的点变成左侧点，原来的“最小斜率”问题转化为镜像后的“最大斜率”问题，于是复用求 $d_R(u)$ 的过程即可。

得到每个 $u$ 的最优向右射线和最优向左射线后，需要判断它们能否挡住某个查询点。

向右射线对应一条直线 $f_u(X)=k_uX+b_u$，但只在 $X\ge X_u$ 时有效。

对所有上半平面的同色查询点 $q$，需要判断：

$$ \max_{u,X_u < X_q} f_u(X_q) > Y_q $$

可以离线扫描完成：

1. 将所有向右射线按照起点 $X_u$ 从小到大排序；
2. 将所有查询点 $q$ 按照 $X_q$ 从小到大排序；
3. 从左到右扫描查询点；
4. 当某条射线满足 $X_u
5. 查询当前 $X_q$ 处的最大值。

这里的数据结构可以使用离散李超树。因为只会在所有查询点的 $X_q$ 上查询，所以李超树只需要建立在这些离散横坐标上。

每条直线插入一次，每个查询点查询一次，复杂度为 $O(n\log n)$。

向左射线完全对称：按照 $X$ 从大到小扫描，当射线满足 $X_u>X_q$ 时加入李超树，查询当前 $X_q$ 处的最大值即可。

如果某次查询得到的最大值大于 $Y_q$，就得到一个答案四元组 $p,q,x,y$，其中 $x,y$ 是该阻挡物对应的两个异色点。

5. 下半平面与正确性

对于满足 $Y_q<0$ 的同色查询点，从 $p$ 到 $q$ 对应于变换平面中从 $Y=-\infty$ 向上走到 $Y_q$。

这时需要找最低的阻挡物。

为了复用上半平面的算法，可以把所有变换后的点做一次反射：

$$ (X,Y)\mapsto (X,-Y) $$

反射后，原来的下半平面查询点变成新的上半平面查询点，然后完全按照上一节处理即可。

因此，check(p) 做两次上半平面检查：

1. 在原变换坐标中处理 $Y_q>0$ 的查询；
2. 将所有点的 $Y$ 取反后，再处理新的 $Y_q>0$ 查询。

下面说明固定点检查的正确性。

如果算法找到某个同色点 $q$，以及一个由两个异色点 $x,y$ 生成的阻挡物，使得在 $X=X_q$ 这条竖直线上，该阻挡物位于 $q'$ 的前方，那么原平面中线段 $pq$ 必然与异色线段 $xy$ 严格相交，所以得到的是合法答案。

反过来，假设存在包含 $p$ 的答案 $p,q,x,y$，其中 $p,q$ 同色，$x,y$ 异色，并且 $pq\cap xy\ne\varnothing$。

考虑 $q$ 所在的半平面。

如果 $q$ 在上半平面，那么在变换平面中，异色线段 $xy$ 一定会在竖直线 $X=X_q$ 上挡在 $q'$ 前方。

如果 $x,y$ 都在 $U$，那么它们对应的线段被 $U'$ 的上凸壳覆盖，所以上凸壳检查一定能找到不低于它的阻挡物。

如果 $x,y$ 分别在 $U,D$，设上半平面端点为 $u$。那么这条异色线段对应从 $u'$ 出发的一条射线。

如果它是向右射线，则为 $u$ 保留的 $d_R(u)$ 斜率最大，因此在所有有效位置上高度不低于原射线。

如果它是向左射线，则为 $u$ 保留的 $d_L(u)$ 斜率最小，因此在所有有效位置上高度不低于原射线。

所以压缩后的候选阻挡物一定也能挡住 $q'$。

下半平面同理，通过 $Y\mapsto -Y$ 反射后转化为同样的问题。

因此固定点检查正确。

6. 完整算法与复杂度

设 A 为左括号点集合，B 为右括号点集合。

如果 $|A|<2$ 或 $|B|<2$，则不可能存在两条同色线段，直接输出 $-1$。

否则：

1. 任取一个 A 类点 $a$，执行 check(a,A,B)，其中 A 是同色点集合，B 是异色点集合。如果成功，输出答案。
2. 如果失败，任取一个 B 类点 $b$，执行 check(b,B,A)。如果成功，输出答案。
3. 如果两次都失败，输出 $-1$。

正确性来自关键结论：如果存在答案，那么要么所有 A 类点都是好点，要么所有 B 类点都是好点。

复杂度方面，单次固定点检查中：

• 建立局部坐标并做射影变换需要 $O(n)$；
• 求 $U'$ 的上凸壳需要 $O(n\log n)$；
• 求所有 $d_R(u)$ 和 $d_L(u)$ 需要 $O(n\log n)$；
• 用李超树查询左右射线需要 $O(n\log n)$；
• 下半平面通过 $Y\mapsto -Y$ 反射后再做一次同样的过程，仍然是 $O(n\log n)$。

所以： $$ \texttt{check}(p)=O(n\log n) $$ 全局只检查两个点，因此总复杂度为：

$$ O(n\log n) $$

空间复杂度为 $O(n)$。