圆（Circles）

题目背景

传说中有若干个魔法圆隐藏在二维平面中。天空中的星星都位于这些圆的圆周上。你拥有一架魔法望远镜，每使用一次，它会返回某一个圆周上的一个随机点。

你的任务是尽量少使用望远镜，找出所有魔法圆的圆心和半径。

本题为交互题。

交互协议

评测程序开始时，会先向你的程序输出一个整数 $K$，表示隐藏圆的个数。

随后你的程序可以进行两类操作。

1. 询问一颗星星

输出一行：

?

并刷新输出缓冲区。评测程序会返回两个实数：

x y

表示一颗星星的坐标。该星星位于某一个隐藏圆的圆周上。

询问次数不得超过 $100000$。

2. 提交一个圆

输出一行：

! cx cy r

表示你认为存在一个圆心为 $(cx,cy)$、半径为 $r$ 的隐藏圆。

你必须恰好提交 $K$ 个圆。提交第 $K$ 个圆之后，评测程序会立即检查答案并结束交互。

通信版 circle.h

为了方便从原题的函数式交互写法迁移，本题下发了 circle.h。如果你使用该头文件，则只需要实现：

void solve(int k);

并可以在 solve 中调用：

std::pair<double, double> sample_star();
void answer(double cen_x, double cen_y, double radius);

其中：

• sample_star() 会自动输出 ? 并读取返回点；
• answer(cx, cy, r) 会自动输出一行 ! cx cy r；
• 你不需要自己编写 main 函数。

你也可以不使用 circle.h，直接按照上面的标准交互协议编写完整程序。

输出刷新

每次输出 ? 或 ! cx cy r 后，都应刷新输出缓冲区。使用 C++ 时，可以使用：

cout << "?" << endl;

或：

cout << "?\n" << flush;

限制

• $2 \le K \le 20$。
• 询问次数 $Q \le 100000$。
• 所有隐藏圆的圆心坐标和半径的绝对值均不超过 $500000$。
• 你提交的圆心坐标和半径也必须满足上述范围。
• 半径必须为正数。
• 任意两个隐藏圆的圆心之间的欧几里得距离大于 $100$。
• 对于评测程序返回的每个星星点，保证它到某个隐藏圆圆周的最短距离小于 $10^{-4}$。

判定与评分

设真实圆为 $(x,y,r)$，你提交的某个圆为 $(x',y',r')$。

如果无法将你提交的 $K$ 个圆与真实的 $K$ 个圆一一配对，使得每一对都满足：

$$|x-x'| \le 10^{-3},\quad |y-y'| \le 10^{-3},\quad |r-r'| \le 10^{-3},$$

则该测试点得分为 $0$。

否则，设你调用 sample_star 的次数为 $Q$，该测试点得分比例为：

$$0.3+0.7\sqrt{\frac{500}{\max(Q,500)}}.$$

每个子任务的得分等于该子任务内所有测试点得分比例的最小值乘以该子任务分值。

子任务

子任务	分值	限制
1	10	$K=2$，且两个圆不相交
2	20	$K=2$
3	13	$K=5$
4	20	$K=10$
5	37	$K\le 20$

交互示例

假设 $K=2$，隐藏圆为：

• 圆 1：圆心 $(100,200)$，半径 $50$；
• 圆 2：圆心 $(-150,-300)$，半径 $75$。

一种可能的交互如下：

评测程序输出：
2

你的程序输出：
?

评测程序输出：
50.4373 206.5988

你的程序输出：
?

评测程序输出：
-79.3886 -274.7206

你的程序输出：
! 100.0 200.0 50.0

你的程序输出：
! -150.0 -300.0 75.0

注意：示例中的星星坐标只是说明交互形式，实际返回值由评测程序随机生成。

@下发文件