题意回顾

• 正 $n$ 边形，顶点 $0$ 到 $n-1$ 顺时针排列。
• 给定三角剖分（$n-3$ 条对角线）。
• 顶点 $0$ 到对角线 $(a,b)$ 的距离定义为：
  • 从 $0$ 顺时针走到 $a$ 或 $b$ 的步数（取较小值） → $\text{left\_distance}$
  • 从 $0$ 逆时针走到 $a$ 或 $b$ 的步数（取较小值） → $\text{right\_distance}$
  • 距离 $= \max(\text{left\_distance}, \text{right\_distance})$
• 目标：用尽量少的 query(x,y) 找到距离顶点 $0$ 最近的对角线。

核心思路

1. 距离的几何意义

对于一条对角线 $(a,b)$，距离顶点 $0$ 最近意味着：

• 在顺时针方向，$0$ 离 $a$ 或 $b$ 很近；
• 在逆时针方向，$0$ 离另一个端点也很近。

换句话说，$a$ 和 $b$ 应该一个在 $0$ 的“左边”附近，一个在 $0$ 的“右边”附近。

2. 最近对角线的结构

在三角剖分中，顶点 $0$ 会与若干个顶点连接（至少与两个顶点有边：$1$ 和 $n-1$ 是多边形的边，还可能与其它顶点有对角线）。

关键性质：距离顶点 $0$ 最近的对角线 $(a,b)$ 一定满足：

• $a \in \{1, 2, \dots, k\}$（顺时针方向前 $k$ 个顶点）
• $b \in \{n-1, n-2, \dots, n-k\}$（逆时针方向前 $k$ 个顶点）

其中 $k$ 是这条对角线的距离值。

3. 高效查找策略

我们可以从小到大枚举距离 $k$，检查是否存在对角线满足上述条件：

• 对 $k = 1, 2, \dots$：
  • 检查所有 $(i, n-k+i-1)$ 组合（$i = 1 \dots k$）
  • 即检查 $(1, n-k), (2, n-k+1), \dots, (k, n-1)$ 这些顶点对
  • 一旦发现某对顶点之间有对角线，它就是距离 $k$ 的对角线，且是全局最近的

4. 算法步骤

function solve(n):
  for k from 1 to floor(n/2):
    for i from 1 to k:
      a = i
      b = n - k + i - 1
      if query(a, b) == 1:
        return a * n + b
  # 理论上不会执行到这里，因为三角剖分中一定存在这样的对角线

5. 查询次数分析

• 第 1 轮检查 1 对
• 第 2 轮检查 2 对
• ...
• 第 k 轮检查 k 对

总查询次数 = $1 + 2 + \dots + k_{\max}$，其中 $k_{\max}$ 是最近对角线的距离值。

由于 $k_{\max} \le \lfloor n/2 \rfloor$，最坏情况下总查询次数约为 $n^2/8$。

对于 $n \le 100$，这完全可行（最多约 1275 次查询，而限制 $w = 4850$）。

6. 正确性证明

• 三角剖分中，顶点 $0$ 所在的三角形至少有一条边是对角线
• 这条对角线的两个端点分布在 $0$ 的两侧
• 当 $k$ 从小到大枚举时，我们找到的第一条对角线就是距离最小的

总结

这道题的解法简洁而有效：

1. 理解距离定义：对角线两端点分布在 $0$ 的两侧近邻
2. 枚举距离：从小到大检查可能的对角线
3. 早期终止：找到第一条对角线即为答案

这种方法在保证正确性的同时，查询次数远低于题目上限，是一个优雅的解决方案。