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,2,\ldots,N)$ の並べ替え）が存在するか判定せよ。存在するならば 1 つ求めよ。

各整数 $i$ ($1$ から $N$ まで) について、線分 $i$ を $P_i$ と $Q_{R_i}$ を結ぶ線分とする。すると、任意の $i$ と $j$ $(1 \leq i < j \leq N)$ に対して、線分 $i$ と線分 $j$ は交差しない。

输入格式

入力は標準入力から次の形式で与えられる。 $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$ を空白で区切って出力せよ。解が複数ある場合は任意のものを出力してよい。

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

2 1 3

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

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)$ 異なる三点が同一直線上に並ぶことはない。 すべての入力値は整数である。点は次の図のように配置されている。 $R = (2, 1, 3)$ とすると 3 本の線分は互いに交差しない。また、$R = (1, 2, 3)$、$(1, 3, 2)$、$(2, 3, 1)$、$(3, 1, 2)$ のいずれも有効な答えである。

标签: AtCoder|abc373G

来源

AtCoder|abc373G