#P1901. Hypertransmission

Hypertransmission

描述描述
银河联邦总统近日决定,银河系的所有行星都必须建立超无线电中心来播放各自的节目。为保障这一进程,政府与知名的超无线电设备制造商“特洛伊木马有限公司”签订了合同。根据合同条款,该公司需为联邦的每颗行星提供一台超发射器,共计NN台。

据悉,银河系中存在两大主要政治运动:工业主义与生态主义,每颗行星上均由其中一派占据主导地位。显然,在行星上建成超无线电站后,该电台的政治节目将支持该行星上的主导政治运动。

特洛伊木马公司提供的所有发射器将具有相同的射程,因此每颗行星的超无线电节目可在距离其不超过RR秒差距的范围内被接收。由于该公司的董事实则是黑暗帝国的特工,他希望通过选择合适的RR来破坏银河联邦的政治局势。

具体来说,对于每颗行星AA,设N+(A)N^+(A)为与AA政治立场相同且能接收到AA节目(含AA自身)的行星数量,N(A)N^-(A)为政治立场相异且能接收到AA节目(含AA自身)的行星数量。若N+(A)<N(A)N^+(A) < N^-(A),则称行星AA为“不稳定行星”。

你的任务是确定一个RR,使得不稳定行星的数量DD达到最大值。由于增加发射器射程会消耗更多制造资源,你需要找到使DD最大的最小RR值。

输入输入
输入首行包含整数NN1N10001 \leq N \leq 1000),表示银河联邦的行星总数。接下来NN行每行包含四个整数xi,yi,zi,pix_i, y_i, z_i, p_i,依次描述各行星的信息:xi,yi,zix_i, y_i, z_i为行星的空间坐标,pi=0p_i = 0表示工业主义主导,pi=1p_i = 1表示生态主义主导。所有坐标的绝对值不超过1000010000,且任意两颗行星的位置均不重合。

输出输出
首先输出DD,即可能的最大不稳定行星数量;第二行输出非负实数RR,即使DD取得最大值的最小射程。RR的计算精度需满足与正确值的误差不超过10410^{-4}

输入数据

4
0 0 0 1
0 1 0 0
1 0 0 0
1 1 0 1

输出数据

4
1.0000