loj#P3374. 「eJOI2020」三角剖分
「eJOI2020」三角剖分
题目描述
本题译自 eJOI2020 Problem B. Triangulation
注意:在 LibreOJ 上,由于语言限制,目前只支持 C++ 语言的提交。
Anna 画了一个正 边形,多边形的 个顶点分别用 到 的整数顺时针编号。之后她画了 条对角线对其进行了三角剖分,这 条对角线除多边形顶点以外没有任何交点。对角线指的是连接多边形两个不同且不相邻顶点的线段。
首先,定义顶点 到对角线 的距离。假设从顶点 开始,沿顺时针方向不断移动至下一个顶点,直到到达对角线 的某个端点,所经过的边数称为 left_distance
。类似地,从 开始沿逆时针方向移动,直到移动到对角线 的某个端点,所经过的边数称为 right_distance
。从 到 的距离是 left_distance
与 right_distance
的最大值。
在这个样例图中,从顶点 到对角线 的距离是 ,left_distance
是 ,right_distance
是 。从 到对角线 的距离是 ,left_distance
是 ,right_distance
是 。
Anna 想给 Jacob 一个挑战性的任务。Jacob 不知道现在画了哪些对角线。他只知道 的值,但是他可以多次询问 Anna 某些对顶点的信息,Anna 会告诉他在这些对顶点之间是否存在对角线。Jacob 的任务是找到距离顶点 最近(距离的定义如上所述)的对角线。你需要帮助他在有限次数的询问后回答 Anna 的问题。
实现细节
你需要在提交中引入 triangulation.h
头文件,并实现如下函数:
-
- 这个函数会被
grader
恰好调用一次。 - :多边形的顶点数。
- 如果答案为对角线 离顶点 最近,则函数应返回 。
- 如果有多条对角线离顶点 最近,你可以返回其中的任意一条。
- 这个函数会被
上述函数可以调用以下函数:
-
- :第一个顶点的编号。
- :第二个顶点的编号。
- 如果 与 之间有一条对角线,则返回 ,否则返回 。
数据范围与提示
对于全部数据,。
令 为你在单组测试数据上询问的总数。令 。
- 如果你的询问不合法或你的答案错误,你会获得该测试点 的分数;
- 如果 ,你会获得该测试点 的分数;
- 如果 ,你会获得该测试点 的分数;
- 如果 ,你会获得该测试点 的分数;
本题只有一组子任务,你的得分是每组测试数据得分之和。