103736: [Atcoder]ABC373 G - No Cross Matching
Description
Score : $600$ points
Problem Statement
There are $2N$ points $P_1,P_2,\ldots,P_N, Q_1,Q_2,\ldots,Q_N$ on a two-dimensional plane. The coordinates of $P_i$ are $(A_i, B_i)$, and the coordinates of $Q_i$ are $(C_i, D_i)$. No three different points lie on the same straight line.
Determine whether there exists a permutation $R = (R_1, R_2, \ldots, R_N)$ of $(1, 2, \ldots, N)$ that satisfies the following condition. If such an $R$ exists, find one.
- For each integer $i$ from $1$ through $N$, let segment $i$ be the line segment connecting $P_i$ and $Q_{R_i}$. Then, segment $i$ and segment $j$ $(1 \leq i < j \leq N)$ never intersect.
Constraints
- $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)$
- No three different points lie on the same straight line.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$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$
Output
If there is no $R$ satisfying the condition, print -1
.
If such an $R$ exists, print $R_1, R_2, \ldots, R_N$ separated by spaces. If there are multiple solutions, you may print any of them.
Sample Input 1
3 0 0 2 4 4 2 0 2 2 0 4 4
Sample Output 1
2 1 3
The points are arranged as shown in the following figure.
By setting $R = (2, 1, 3)$, the three line segments do not cross each other. Also, any of $R = (1, 2, 3)$, $(1, 3, 2)$, $(2, 3, 1)$, and $(3, 1, 2)$ is a valid answer.
Sample Input 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
Sample Output 2
3 5 8 2 7 4 6 1
Output
得分:600分
问题陈述
在二维平面上有$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)$满足以下条件。如果存在这样的$R$,找出一个。
- 对于从1到$N$的每个整数$i$,设线段$i$为连接$P_i$和$Q_{R_i}$的线段。那么,线段$i$和线段$j$($1 \leq i < j \leq N$)永远不会相交。
约束条件
- $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$)
- 没有三个不同的点在同一直线上。
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出:
$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$,打印$R_1, R_2, \ldots, R_N$,用空格分隔。如果有多个解,你可以打印其中任何一个。
样本输入1
3 0 0 2 4 4 2 0 2 2 0 4 4
样本输出1
2 1 3
点的排列如下图中所示。
通过设置$R = (2, 1, 3)$,三个线段不会相互交叉。另外,$R = (1, 2, 3)$,$(1, 3, 2)$,$(2, 3, 1)$和$(3, 1, 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