Chords

题目描述

圆上有 $2N$ 个等间距放置的点，按顺时针方向从某一点开始编号为 $1$ 到 $2N$。 圆上还有 $N$ 条弦，第 $i$ 条弦连接点 $A_i$ 和 $B_i$。 保证所有值 $A_1,\dots,A_N,B_1,\dots,B_N$ 两两不同。 判定是否存在两条弦相交。

输入格式

输入由标准输入提供，格式如下： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

如果存在两条弦相交，输出 $Yes$；否则输出 $No$。

3
1 3
4 2
5 6

Yes

3
6 1
4 3
2 5

No

4
2 4
3 7
8 6
5 1

Yes

提示

$2\leq N \leq 2\times 10^5$ $1\leq A_i,B_i \leq 2N$ $A_1,\dots,A_N,B_1,\dots,B_N$ 两两不同 所有输入值均为整数 如图所示，弦 $1$（连接点 $1$ 和 $3$ 的线段）和弦 $2$（连接点 $4$ 和 $2$ 的线段）相交，所以输出 $Yes$.
如图所示，弦之间没有相交，所以输出 $No$.

标签: AtCoder|abc338E

来源

AtCoder|abc338E