← 返回题目列表

Codeforces · 1776/I

I. 菠菜披萨

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

阿尔贝托和比阿特丽斯两兄妹必须一起吃菠菜披萨。不过,他们都不喜欢吃菠菜,所以他们都想尽量少吃。

披萨具有严格凸多边形的形状,$$$n$$$ 顶点位于平面的整数坐标 $$$(x_1, y_1), \, (x_2, y_2), \, \dots, \, (x_n, y_n)$$$ 处。

兄弟姐妹决定按照以下方式吃披萨:轮流从阿尔贝托开始,每个兄弟姐妹选择披萨剩余部分的一个顶点,并吃掉由其两个相邻边确定的三角形。这样,在第一个 $$$n - 3$$$ 的每一圈之后,披萨都会少一个顶点。游戏在第 $$$(n - 2)$$$ 回合后结束,此时所有披萨都已吃完。

假设阿尔贝托和比阿特丽斯选择最佳吃的披萨,哪一个兄弟姐妹能吃掉最多一半的披萨?您应该找到一个有这样做策略的兄弟姐妹,并帮助他们适当地选择切片。请注意,如果阿尔贝托和比阿特丽斯选择最佳切片,他们最终可能会吃掉一半的区域。

输入

第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 100$$$) — 顶点数。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — 代表披萨初始形状的多边形第 $$$i$$$ 顶点的坐标。

保证多边形是严格凸的,并且其顶点按逆时针顺序给出。

互动

首先,您应该打印一行,其中包含字符串 $$$\texttt{Alberto}$$$ 或字符串 $$$\texttt{Beatrice}$$$ — 您将帮助赢得的兄弟姐妹。

然后,在接下来的 $$$n - 2$$$ 轮中,您将与法官轮流选择一片披萨并将其取出,如果您选择帮助阿尔贝托,则从您开始,或者如果您选择帮助比阿特丽斯,则从法官开始。

- 当轮到你的时候,打印一行包含一个之前没有选择过的整数 $$$p$$$ ($$$1 \leq p \leq n$$$) ,表示你想吃掉位于 $$$(x_p, y_p)$$$ 处的顶点确定的切片。
- 轮到裁判时,读取一个整数$$$q$$$ ($$$1 \leq q \leq n$$$),表示对方吃掉位于$$$(x_q, y_q)$$$处的顶点确定的切片。保证 $$$q$$$ 之前没有被选择过。

如果您的交互之一格式错误,则交互器会立即终止,并且您的程序会收到判决 $$$\texttt{WRONG-ANSWER}$$$。否则,如果最后您的玩家最多吃掉了一半的披萨,您将收到 $$$\texttt{CORRECT}$$$,否则您将收到 $$$\texttt{WRONG-ANSWER}$$$。

打印一行后,不要忘记结束该行并刷新输出。否则,您将得到判决$$$\texttt{TIMELIMIT}$$$。要刷新输出,请使用:

- C 中的 $$$\texttt{fflush(stdout)}$$$;
- C++ 中的 $$$\texttt{fflush(stdout)}$$$、$$$\texttt{cout <}\texttt{<lush}$$$ 或 $$$\texttt{cout.flush()}$$$;
- Java 和 Kotlin 中的 $$$\texttt{System.out.flush()}$$$;
- Python 中的 $$$\texttt{sys.stdout.flush()}$$$。

示例

输入 #1

4
0 0
6 1
5 3
1 4

输出 #1

-

输入 #2

6
0 0
2 0
3 2
2 4
0 4
-1 2

输出 #2

-

输入 #3

7
0 0
2 0
5 2
4 5
1 5
-1 4
-1 2

输出 #3

-

注意

在第一个示例中,披萨的面积为 $$$15$$$。通过吃顶点 $$$2$$$ 周围(面积 $$$6.5$$$)或顶点 $$$3$$$ 周围(面积 $$$3.5$$$)周围的切片,Alberto 可以吃掉不到一半的披萨。

在第二个样本中,可以证明,如果两个玩家吃得最佳,他们将恰好吃掉一半的披萨。因此,可以选择帮助阿尔贝托或贝阿特丽斯。

在第三个样本中,可以表明只有 Beatrice 有最多吃掉一半披萨的策略。以下是有效交互的示例(读取输入后):

$$$$$$ \begin{array}{|c|c|c|} \hline \textbf{参赛者} & \textbf{裁判} & \textbf{解释} \\ \hline \texttt{Beatrice} & & \text{参赛者将帮助 Beatrice} \\ \hline & \texttt{7} & \text{Alberto 吃掉三角形顶点 $6$、$7$、$1$ 和面积 $1$} \\ \hline \texttt{2} & & \text{Beatrice 吃掉顶点 $1$、$2$、$3$ 和面积 $2$的三角形} \\ \hline & \texttt{5} & \text{Alberto 吃掉顶点 $4$、$5$、$6$ 和面积 $1.5$的三角形} \\ \hline \texttt{4} & & \text{Beatrice 吃掉了顶点为 $3$、$4$、$6$ 且面积为 $8$的三角形} \\ \hline & \texttt{6} & \text{Alberto 吃掉了顶点为 $3$、$6$、$1$ 且面积为 $11$的三角形} \\ \hline \end{array} $$$$$$ Alberto 吃掉的总面积为$$$13.5$$$,Beatrice吃掉的总面积是$$$10$$$,不到整个披萨面积的一半。在这个交互示例中,参赛者和评委执行的动作可能不是最佳的。该过程如下图所示: