Spinach Pizza

题目描述

The two siblings Alberto and Beatrice have to eat a spinach pizza together. However, none of them likes spinach, so they both want to eat as little as possible. The pizza has the shape of a strictly convex polygon with $ n $ vertices located at integer coordinates $ (x_1, y_1), \, (x_2, y_2), \, \dots, \, (x_n, y_n) $ of the plane. The siblings have decided to eat the pizza in the following way: taking turns, starting with Alberto, each sibling chooses a vertex of the remaining part of the pizza and eats out the triangle determined by its two neighboring edges. In this way, after each of the first $ n - 3 $ turns the pizza will have one less vertex. The game ends after the $ (n - 2) $ -th turn, when all the pizza has been eaten. Assuming that Alberto and Beatrice choose the slices to eat optimally, which of the siblings manages to eat at most half of the pizza? You should identify a sibling that has a strategy to do so and help them choose the slices appropriately. Note that it is possible that both Alberto and Beatrice end up eating exactly half of the area if they choose their slices optimally.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 4 \le n \le 100 $ ) — the number of vertices. The next $ n $ lines contain two integers $ x_i $ and $ y_i $ each ( $ -10^6 \le x_i, y_i \le 10^6 $ ) — the coordinates of the $ i $ -th vertex of the polygon representing the initial shape of the pizza. It is guaranteed that the polygon is strictly convex and that its vertices are given in counterclockwise order.

输出格式

First, you should print a line containing either the string $ \texttt{Alberto} $ or the string $ \texttt{Beatrice} $ — the sibling that you will help to win. Then, for the next $ n - 2 $ turns, you will alternate with the judge in choosing a slice of the pizza and removing it, starting with you if you chose to help Alberto, or starting with the judge if you chose to help Beatrice. - When it is your turn, print a single line containing an integer $ p $ ( $ 1 \leq p \leq n $ ) that has not been chosen before, indicating that you want to eat the slice determined by the vertex located at $ (x_p, y_p) $ . - When it is the judge's turn, read an integer $ q $ ( $ 1 \leq q \leq n $ ), indicating that the other player eats the slice determined by the vertex located at $ (x_q, y_q) $ . It is guaranteed that $ q $ has not been chosen before. If one of your interactions is malformed, the interactor terminates immediately and your program receives the verdict $ \texttt{WRONG-ANSWER} $ . Otherwise, you will receive $ \texttt{CORRECT} $ if at the end your player has eaten at most half of the pizza, and $ \texttt{WRONG-ANSWER} $ otherwise. After printing a line do not forget to end the line and flush the output. Otherwise, you will get the verdict $ \texttt{TIMELIMIT} $ . To flush the output, use: - $ \texttt{fflush(stdout)} $ in C; - $ \texttt{fflush(stdout)} $ , $ \texttt{cout <}\texttt{< flush} $ or $ \texttt{cout.flush()} $ in C++; - $ \texttt{System.out.flush()} $ in Java and Kotlin; - $ \texttt{sys.stdout.flush()} $ in Python.

输入输出样例

输入样例 #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

-

说明

In the first sample, the pizza has area $ 15 $ . Alberto can eat less than half of the pizza by eating the slice around vertex $ 2 $ (which has area $ 6.5 $ ) or around vertex $ 3 $ (which has area $ 3.5 $ ). In the second sample, it can be proved that both players will eat exactly half of the pizza if they eat optimally. Therefore it is possible to choose to help either Alberto or Beatrice. In the third sample, it is possible to show that only Beatrice has a strategy to eat at most half of the pizza. The following is an example of a valid interaction (after reading the input): $ $ \begin{array}{|c|c|c|} \hline \textbf{Contestant} & \textbf{Judge} & \textbf{Explanation} \\ \hline \texttt{Beatrice} & & \text{The contestant will help Beatrice} \\ \hline & \texttt{7} & \text{Alberto eats the triangle with vertices $6$, $7$, $1$ and area $1$} \\ \hline \texttt{2} & & \text{Beatrice eats the triangle with vertices $1$, $2$, $3$ and area $2$} \\ \hline & \texttt{5} & \text{Alberto eats the triangle with vertices $4$, $5$, $6$ and area $1.5$} \\ \hline \texttt{4} & & \text{Beatrice eats the triangle with vertices $3$, $4$, $6$ and area $8$} \\ \hline & \texttt{6} & \text{Alberto eats the triangle with vertices $3$, $6$, $1$ and area $11$} \\ \hline \end{array} $ $ The total area eaten by Alberto is $ 13.5 $ and the total area eaten by Beatrice is $ 10$, which is less than half the area of the whole pizza. The actions performed by the contestant and the judge in this example of interaction may be non-optimal. The process is illustrated below: 

**菠菜披萨**

**题目描述：**
阿尔贝托和比阿特丽斯两兄妹要一起吃一个菠菜披萨。然而，他们俩都不喜欢菠菜，所以都希望能吃得尽可能少。

披萨的形状是一个严格凸多边形，有 $ 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 << flush} $ 或 $ \texttt{cout.flush()} $ ；
- 在 Java 和 Kotlin 语言中使用 $ \texttt{System.out.flush()} $ ；
- 在 Python 语言中使用 $ \texttt{sys.stdout.flush()} $ 。**菠菜披萨** **题目描述：** 阿尔贝托和比阿特丽斯两兄妹要一起吃一个菠菜披萨。然而，他们俩都不喜欢菠菜，所以都希望能吃得尽可能少。 披萨的形状是一个严格凸多边形，有 $ 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 << flush} $ 或 $ \texttt{cout.flush()} $ ； - 在 Java 和 Kotlin 语言中使用 $ \texttt{System.out.flush()} $ ； - 在 Python 语言中使用 $ \texttt{sys.stdout.flush()} $ 。