AT_abc338_e [ABC338E] 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。

输入输出样例 #1

输入 #1

3
1 3
4 2
5 6

输出 #1

Yes

输入输出样例 #2

输入 #2

3
6 1
4 3
2 5

输出 #2

No

输入输出样例 #3

输入 #3

4
2 4
3 7
8 6
5 1

输出 #3

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$（连接点 $1$ 和点 $3$ 的线段）与弦 $2$（连接点 $4$ 和点 $2$ 的线段）相交，因此输出 Yes。

样例解释 2

如图所示，没有任意两条弦相交，因此输出 No。

由 ChatGPT 4.1 翻译