该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3201.zip](file://AdditionalFile3201.zip?type=additional_file)

#3201. 「CEOI2018」三角形

标签: 交互 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

译自 CEOI2018 Day2 T3. Triangles

Byteland 是一个有着 $n\ (n\ge 3)$ 个城市的美好国家，它可以用 $n$ 个二维平面上不同的点来表示。城市编号为 $1$ 到 $n$。作为一个有课，你不知道 Byteland 中城市的确切位置。从一本旅游杂志上你知道了没有任意三个城市共线。

$n$ 个点的点集的凸包是一个面积最小的凸多边形，满足所有 $n$ 个点都在这个多边形的内部或边界上。一个凸多边形的内角均小于 $180$ 度，并且不自交。

你的任务是找到 Byteland 的城市所构成的凸包边界上有多少个点。你只能询问由三个不同的整数构成的一些三元组 $i,j,k\ (1\le i,j,k\le n)$。这样的问题有关于由城市 $i,j,k$ 所组成的三角形。这个问题的答案是如果按 $i,j,k$ 的顺序遍历这个三角形，是顺时针顺序还是逆时针顺序。

交互过程

在 LibreOJ 上，本题只支持 C++ 语言的提交。

你的程序应该使用提供的库实现主函数。库（为 C++ 语言提供的是 trilib.h）提供了如下函数：

• int get_n();
  返回城市个数。
• bool is_clockwise(int a, int b, int c);
  如果三个点 $a,b,c\ (1\le a,b,c\le n,a\neq b\neq c\neq a)$ 以顺时针顺序给出，则返回 true，如果以逆时针顺序给出，则返回 false。
• void give_answer(int s);

在你的程序调用 give_answer 后，就不允许再调用任何询问函数了。你只能调用 give_answer 函数恰好一次。

本题中，你不允许从标准读入中读取输入，或输出到标准输出中。在调用 give_answer 后，你的程序应立刻停止。

你可以假设点的位置是提前确定的，并且在程序运行中不会改变（换句话说，库的行为是确定的）。例如，在样例中（见下）调用 give_answer(4) 并立即结束是可以通过这组数据的。你的程序允许在确定答案之前猜测答案。

样例交互

考虑 $n=6$ 个城市，位置分别在 $(1,1),(4,3),(2,2),(1,4),(5,1),(3,2)$，如下图所示。凸包已经用线标识出来了。在边界上包含 $4$ 个点，所以答案是 $4$。

下表展示了一个对于样例的样例交互过程。

下图展示了第一个询问中的三角形。城市 $1,4,2$ 是按顺时针顺序给出的，所以返回 true。

数据范围与提示

对于所有测试数据，$3\le n\le 4\times 10^4$，你可以调用 is_clockwise 函数最多 $10^6$ 次。