← 返回题目列表

AtCoder · abc373_g

G. 无交叉匹配

中文机器翻译题面 查看原题

分数: 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) of (1, 2, \ldots, N) 满足以下条件。如果这样一个 R 存在,请找到一个。

  • 对于每个整数 i 来自 1 通过 N,让分段 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