#P18412. Keychain
Keychain
Keychain
在二维平面上给定 个点 。以 为圆心画圆 ,所有圆的半径均为 。
求最小的 ,使得存在另一个广义圆 ,与所有 个圆都相交;同时给出一个这样的 。
- 半径为 的圆是到圆心的欧氏距离恰好等于 的点集,指圆周;允许 。
- 广义圆可以是一个圆,也可以是一条直线。
- 两个对象相交,指它们有公共点。
输入格式
第一行一个整数 ()。
接下来 行,每行两个整数 ,表示 的坐标()。保证任意两个给定点不同。
输出格式
第一行输出最优答案 ,必须满足 。可以证明最小值存在,且在此范围内。
设 在 时与全部 相交。可以证明,在本题限制下,总能选择有理坐标圆心的圆,或具有整数系数的直线。
如果输出圆,下一行输出:
C X Y Z r
表示圆心为 ,半径为 。 必须是绝对值不超过 的整数,; 是满足 的实数。
如果输出直线,下一行输出:
L a b c
表示 。 必须是绝对值不超过 的整数,且 不同时为零。
判题首先检查方案是否与所有圆周相交。令 :
- 对圆方案,圆心记为 ,对每个 检查
- 对直线方案,检查每个 都满足
随后检查输出的 与参考最优值的绝对误差或相对误差不超过 。相对误差以参考最优值为分母;参考值为零时可用绝对误差条件。边界均为包含等号。可以输出任意符合要求的方案。
原样例
样例 1
输入:
4
2 1
1 3
2 4
7 2
输出:
0.27069063257455492223
C 1152 720 288 2.77069063257455492234
样例 2
输入:
7
26919 7739
85584 91359
47712 21058
13729 26355
16636 96528
88747 93023
46770 1150
输出:
9663.87959749101919015857
C 3605577680770432 5873755742321056 96368792608 50864.33205303458045065668
样例 3
输入:
10
756 624
252 208
504 416
378 312
203 287
329 391
0 0
707 703
126 104
581 599
输出:
46.05915288207108030175
L -1248 1512 90300
说明
前两个样例的原题示意图如下:

注意溢出。原题建议考虑使用 long double 或 __int128。特别是输出圆心可能远在输入坐标范围之外,计算巨大半径时还需避免精度损失。