AT_abc373_g [ABC373G] No Cross Matching

题目描述

在二维平面上有 $2N$ 个点，分别为 $P_1,P_2,\ldots,P_N$ 和 $Q_1,Q_2,\ldots,Q_N$。点 $P_i$ 的坐标为 $(A_i,B_i)$，点 $Q_i$ 的坐标为 $(C_i,D_i)$。不存在同一直线上的三个不同点。

请判断是否存在一个数列 $R=(R_1,R_2,\ldots,R_N)$，它是 $1$ 到 $N$ 的一个排列，并且满足以下条件：

• 对于所有 $1$ 到 $N$ 的整数 $i$，将 $P_i$ 和 $Q_{R_i}$ 作为端点连成线段，要求任意两条线段 $i$ 和 $j$（$1\leq i<j\leq N$）都不相交。

如果存在这样的 $R$，请给出其中一个；如果不存在，输出 $-1$。

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$
$C_1\ D_1$
$C_2\ D_2$
$\vdots$
$C_N\ D_N$

输出格式

如果不存在满足条件的 $R$，输出 $-1$。

如果存在，输出 $R_1,R_2,\ldots,R_N$，用空格分隔。若有多个答案，输出任意一个均可。

输入输出样例 #1

输入 #1

3
0 0
2 4
4 2
0 2
2 0
4 4

输出 #1

2 1 3

输入输出样例 #2

输入 #2

8
59 85
60 57
72 12
3 27
16 58
41 94
77 64
97 20
32 37
7 2
57 94
35 70
38 60
97 100
5 76
38 8

输出 #2

3 5 8 2 7 4 6 1

说明/提示

数据范围

• $1\leq N\leq 300$
• $0\leq A_i,B_i,C_i,D_i\leq 5000$（$1\leq i\leq N$）
• $(A_i,B_i)\neq(A_j,B_j)$（$1\leq i<j\leq N$）
• $(C_i,D_i)\neq(C_j,D_j)$（$1\leq i<j\leq N$）
• $(A_i,B_i)\neq(C_j,D_j)$（$1\leq i,j\leq N$）
• 不存在同一直线上的三个不同点
• 所有输入均为整数

样例解释 1

点的分布如下图所示。

取 $R=(2,1,3)$ 时，三条线段互不相交。实际上，$R$ 取 $(1,2,3)$、$(1,3,2)$、$(2,3,1)$、$(3,1,2)$ 也都是正确答案。

由 ChatGPT 4.1 翻译