题目类型说明

这是一道提交函数题 / 交互式构造题。你需要提交 ruler_compass.cpp，实现指定函数，而不是编写普通的标准输入输出程序。

题目描述

在几何课上，老师给学生出了一道不同寻常的题目：给定平面上的目标点 $(tarx,tary)$，要求从初始点集

$$\{(0,0),(1,0)\}$$

出发，不断向点集中加入新点，直到某个新加入的点与目标点的欧几里得距离不超过 0.001。

每一步加入新点的过程如下：

1. 用直尺和圆规构造两个几何对象，它们可以是：两条直线、两个圆，或者一条直线和一个圆；
2. 求这两个几何对象的交点（如果存在），并把这些交点加入点集；
3. 检查新加入的点中是否存在一个与目标点足够接近；如果有，则报告该点并结束，否则继续下一步。

其中：

• 一条直线由点集中两个已有点确定；
• 一个圆由三个已有点确定：其中一个点作为圆心，另外两个点之间的距离作为半径；
• “足够接近”是指与目标点的欧几里得距离不超过 0.001。

你需要实现的函数

你需要提交文件 ruler_compass.cpp，其中包含函数：

void go(double tarx, double tary);

该函数会被评测程序调用一次，参数为目标点坐标。你的任务是在函数内部通过调用评测器提供的接口，不断构造点，直到得到一个与目标点距离不超过 0.001 的点。

你的源文件可以包含其他辅助函数和全局变量，但不能包含 main() 函数。

点集与接口说明

设当前点集为 $S$，其中每个点都有一个唯一编号。记一个编号为 id、坐标为 $(x,y)$ 的点为：

id:(x,y)

初始时：

S = {0:(0,0), 1:(1,0)}

评测器提供以下接口：

void define_line(int ida, int idb);

定义一条经过编号 ida 与 idb 的点的直线。两点必须不同（距离严格大于 0）。

void define_circle(int idc, int idr1, int idr2);

定义一个圆：圆心为编号 idc 的点，半径等于编号 idr1 与 idr2 的两点间距离。要求这两点间距离严格大于 0。

int intersect(int &id1, double &x1, double &y1,
              int &id2, double &x2, double &y2);

计算最近定义的两个几何对象的交点个数，并返回交点数量，可能为 0、1 或 2。

• 如果两个图形有超过两个交点，则说明它们重合，此次 intersect 调用非法；
• 新产生点的编号与坐标会写入参数 id1,x1,y1,id2,x2,y2 中；
• 新编号总是未被使用过的连续整数；
• 调用 intersect() 后，新生成的点应视为加入点集 $S$，之后可以继续使用。

若只有一个交点，则只有 id1,x1,y1 有意义；若没有交点，则这些输出参数均未定义。

重要： 每次调用 intersect() 前，你都必须先通过两次 define_...() 调用定义好要求交的那两个对象。

当你得到了一个足够接近目标点的点后，应调用：

void done(int id);

向评测器报告该点的编号，并结束你的 go() 函数。

目标总结

你需要实现 go(double tarx, double tary)：

• 从初始点集 S = {0:(0,0), 1:(1,0)} 出发；
• 通过调用 define_line()、define_circle() 和 intersect() 逐步构造新点；
• 直到得到某个点 k:(myx,myy)，满足它与 (tarx,tary) 的距离不超过 0.001；
• 此时调用 done(k) 并结束。

数据范围

• $0 \le tarx, tary < 10000$

评分方式

如果你报告的点 $(myx,myy)$ 与目标点 $(tarx,tary)$ 的距离大于 0.001，该测试点得 0 分。

设你的程序在某个测试点中调用了 intersect() 共 $p$ 次，则该测试点分数为：

$$score = 10 - (p - 45) \times 0.085$$

• 若 score < 0，该测试点得 0 分；
• 若 score > 10，该测试点得 10 分。

分组如下：

• 10% 的测试满足：tary = 0，tarx <= 40，且 tarx 为整数；
• 另 10% 的测试满足：tary = 0，且 tarx 为整数；
• 另 10% 的测试满足：tary = 0，tarx <= 10；
• 另 10% 的测试满足：tary = 0；
• 另 10% 的测试满足：tarx 和 tary 都为整数；
• 每个测试点单独计分。

样例交互

go(1.5, 0.866025404);

// S = {0:(0, 0), 1:(1, 0)}
define_line(0, 1);
define_circle(1, 0, 1);
intersect(id1, x1, y1, id2, x2, y2);

// intersect() 返回 2
// id1 = 2, x1 = 0, y1 = 0 ; id2 = 3, x2 = 2, y2 = 0

// S = {0:(0,0), 1:(1,0), 2:(0,0), 3:(2,0)}
define_circle(1, 1, 3);
define_circle(3, 1, 3);
intersect(id1, x1, y1, id2, x2, y2);

// intersect() 返回 2
// id1 = 4, x1 = 1.5, y1 = 0.866025404 ; id2 = 5, x2 = 1.5, y2 = -0.866025404

done(4);

// OK。2 步 -> 10 分

本地测试说明

选手会得到文件 contestant_grader.cpp 以及一个测试文件 test.00.in，用于本地测试自己实现的 go() 函数。test.00.in 中给出的就是上面样例交互中的目标点。

不要求 contestant_grader 与评测时使用的 grader 完全相同，但保证它们与选手程序的交互行为一致，也会用相同方式计算交点坐标。

关于如何将 contestant_grader.cpp 与你的 go() 一起编译，请阅读系统提供的 README 文件。

---

难度分类（按国内信息学竞赛标准）

难度定位： NOI / 省选风格构造交互题，中档偏上。

评价依据：

这题并不考传统算法模板，而是考尺规构造、几何直觉、交互接口使用以及评分策略下的步数优化。拿到部分分并不太难，但想稳定打高分，需要把整数构造、二进制构造、近似表示、平行线 / 垂线作法等内容整合起来，属于很典型的高水平构造题，不适合作为普通 CSP-S 题目看待。