#P18412. Keychain

Keychain

Keychain

在二维平面上给定 nn 个点 p1,…,pnp_1,\ldots,p_n。以 pip_i 为圆心画圆 CiC_i,所有圆的半径均为 RR。

求最小的 RR,使得存在另一个广义圆 Γ\Gamma,与所有 nn 个圆都相交;同时给出一个这样的 Γ\Gamma。

  • 半径为 rr 的圆是到圆心的欧氏距离恰好等于 rr 的点集,指圆周;允许 r=0r=0。
  • 广义圆可以是一个圆,也可以是一条直线。
  • 两个对象相交,指它们有公共点。

输入格式

第一行一个整数 nn(1≤n≤30001\le n\le3000)。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示 pip_i 的坐标(0≤xi,yi≤1050\le x_i,y_i\le10^5)。保证任意两个给定点不同。

输出格式

第一行输出最优答案 RoptR_{\mathrm{opt}},必须满足 0≤Ropt≤1050\le R_{\mathrm{opt}}\le10^5。可以证明最小值存在,且在此范围内。

设 Γopt\Gamma_{\mathrm{opt}} 在 R=RoptR=R_{\mathrm{opt}} 时与全部 CiC_i 相交。可以证明,在本题限制下,总能选择有理坐标圆心的圆,或具有整数系数的直线。

如果输出圆,下一行输出:

C X Y Z r

表示圆心为 (X/Z,Y/Z)(X/Z,Y/Z),半径为 rr。X,Y,ZX,Y,Z 必须是绝对值不超过 101810^{18} 的整数,Z≠0Z\ne0;rr 是满足 0≤r≤10180\le r\le10^{18} 的实数。

如果输出直线,下一行输出:

L a b c

表示 ax+by=cax+by=c。a,b,ca,b,c 必须是绝对值不超过 101810^{18} 的整数,且 a,ba,b 不同时为零。

判题首先检查方案是否与所有圆周相交。令 ε=10−6\varepsilon=10^{-6}:

  • 对圆方案,圆心记为 OO,对每个 ii 检查∣R−r∣−ε≤d(O,pi)≤R+r+ε.|R-r|-\varepsilon\le d(O,p_i)\le R+r+\varepsilon.
  • 对直线方案,检查每个 ii 都满足d(L,pi)≤R+ε.d(L,p_i)\le R+\varepsilon.

随后检查输出的 RoptR_{\mathrm{opt}} 与参考最优值的绝对误差或相对误差不超过 10−610^{-6}。相对误差以参考最优值为分母;参考值为零时可用绝对误差条件。边界均为包含等号。可以输出任意符合要求的方案。

原样例

样例 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。特别是输出圆心可能远在输入坐标范围之外,计算巨大半径时还需避免精度损失。