题目描述

本题译自 eJOI2020 Problem B. Triangulation

Anna 画了一个正 $n$ 边形，多边形的 $n$ 个顶点分别用 $0$ 到 $n-1$ 的整数顺时针编号。之后她画了 $n-3$ 条对角线对其进行了三角剖分，这 $n-3$ 条对角线除多边形顶点以外没有任何交点。对角线指的是连接多边形两个不同且不相邻顶点的线段。

首先，定义顶点 $A$ 到对角线 $D$ 的距离。假设从顶点 $A$ 开始，沿顺时针方向不断移动至下一个顶点，直到到达对角线 $D$ 的某个端点，所经过的边数称为 $\text{left\_distance}$。类似地，从 $A$ 开始沿逆时针方向移动，直到移动到对角线 $D$ 的某个端点，所经过的边数称为 $\text{right\_distance}$。从 $A$ 到 $D$ 的距离是 $\text{left\_distance}$ 与 $\text{right\_distance}$ 的最大值。

在这个样例图中，从顶点 $0$ 到对角线 $(1,5)$ 的距离是 $2$，$\text{left\_distance}$ 是 $1$，$\text{right\_distance}$ 是 $2$。从 $0$ 到对角线 $(0,5)$ 的距离是 $5$，$\text{left\_distance}$ 是 $5$，$\text{right\_distance}$ 是 $2$。

Anna 想给 Jacob 一个挑战性的任务。Jacob 不知道现在画了哪些对角线。他只知道 $n$ 的值，但是他可以多次询问 Anna 某些对顶点的信息，Anna 会告诉他在这些对顶点之间是否存在对角线。Jacob 的任务是找到距离顶点 $0$ 最近（距离的定义如上所述）的对角线。你需要帮助他在有限次数的询问后回答 Anna 的问题。

实现细节

你需要在提交中引入 triangulation.h 头文件，并实现如下函数：

int solve(int n)

这个函数会被 grader 恰好调用一次。

• n：多边形的顶点数。
• 如果答案为对角线 $(a,b)$ 离顶点 $0$ 最近，则函数应返回 $a \cdot n + b$。
• 如果有多条对角线离顶点 $0$ 最近，你可以返回其中的任意一条。

上述函数可以调用以下函数：

int query(int x, int y)

• x：第一个顶点的编号。
• y：第二个顶点的编号。
• $0 \le x,y \le n-1$
• 如果 $x$ 与 $y$ 之间有一条对角线，则返回 $1$，否则返回 $0$。

数据范围与提示

对于全部数据，$5 \le n \le 100$。

令 $q$ 为你在单组测试数据上询问的总数。令

评分规则：

• 如果你的询问不合法或你的答案错误，你会获得该测试点 $0\%$ 的分数；
• 如果 $w < q$，你会获得该测试点 $0\%$ 的分数；
• 如果 $n < q \le w$，你会获得该测试点 $10 + 60 \cdot \frac{w-q}{w-n} \%$ 的分数；
• 如果 $q \le n$，你会获得该测试点 $100\%$ 的分数；

本题只有一组子任务，你的得分是每组测试数据得分之和。