← 返回题目列表

Codeforces · 1158/D

D. 缠绕折线

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

Vasya 在平面上有 $$$n$$$ 个不同点 $$$A_1、A_2、\ldots A_n$$$。它们中没有三个位于同一行,他希望将它们按某种顺序放置 $$$A_{p_1}, A_{p_2}, \ldots, A_{p_n}$$$,其中 $$$p_1, p_2, \ldots, p_n$$$ - 从 $$$1$$$ 到 $$$n$$$ 的整数排列。

这样做之后,他将在这些点上绘制定向折线,并按所选顺序从每个点到下一个点绘制定向线段。因此,对于所有 $$$1 \leq i \leq n-1$$$,他将从点 $$$A_{p_i}$$$ 到点 $$$A_{p_{i+1}}$$$ 绘制定向线段。他想让这条折线满足$$$2$$$条件:

- 它将是非自相交的,因此任何不是邻居的 $$$2$$$ 线段没有公共点。
- 它将被缠绕。

Vasya 有一个字符串 $$$s$$$,由 $$$(n-2)$$$ 符号“L”或“R”组成。如果$$$i$$$向左转(如果$$$s_i = $$$“L”),则我们将其称为定向折线缠绕;如果$$$s_i = $$$“R”则向右转。更正式地说:第 $$$i$$$ 转弯将在点 $$$A_{p_{i+1}}$$$ 处,其中从点 $$$A_{p_i}$$$ 到点 $$$A_{p_{i+1}}$$$ 的定向线段更改为从点 $$$A_{p_{i+1}}$$$ 到点 $$$A_{p_{i+2}}$$$ 的定向线段。让我们定义向量 $$$\overrightarrow{v_1} = \overrightarrow{A_{p_i} A_{p_{i+1}}}$$$ 和 $$$\overrightarrow{v_2} = \overrightarrow{A_{p_{i+1}} A_{p_{i+2}}}$$$。然后,如果为了将向量 $$$\overrightarrow{v_1}$$$ 旋转尽可能小的角度,使其方向与向量 $$$\overrightarrow{v_2}$$$ 的方向一致,我们需要逆时针转动,那么我们说第 $$$i$$$ 转动是向左,否则是向右。为了更好地理解,请看这张图片和一些转弯示例:

这张图有左转

这张图有右转

给定平面上点 $$$A_1、A_2、\ldots A_n$$$ 的坐标和字符串 $$$s$$$。求 $$$1$$$ 到 $$$n$$$ 整数的排列 $$$p_1, p_2, \ldots, p_n$$$,使得 Vasya 绘制的折线满足两个必要条件。

输入

第一行包含一个整数 $$$n$$$ — 点数 ($$$3 \leq n \leq 2000$$$)。接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$,除以空间 - 平面上点 $$$A_i$$$ 的坐标 ($$$-10^9 \leq x_i, y_i \leq 10^9$$$)。最后一行包含一个字符串$$$s$$$,由符号“L”和“R”组成,长度为$$$(n-2)$$$。保证所有点都不同并且没有三个点位于同一条线上。

输出

如果满足的排列不存在,则打印 $$$-1$$$。在另一种情况下,打印 $$$n$$$ 数字 $$$p_1, p_2, \ldots, p_n$$$ - 找到的排列($$$1 \leq p_i \leq n$$$ 和所有 $$$p_1, p_2, \ldots, p_n$$$ 都是不同的)。如果存在多个解决方案,您可以找到任何一个。

示例

输入 #1

3
1 1
3 1
1 3
L

输出 #1

1 2 3

输入 #2

6
1 0
0 1
0 2
-1 0
-1 -1
2 1
RLLR

输出 #2

6 1 3 4 2 5

注意

这是$$$1$$$测试中带有折线的图片:

正如我们所见,这条折线是非自相交且蜿蜒的,因为拐点 $$$2$$$ 已离开。

这是$$$2$$$测试中带有折线的图片: