弥明是白茶的好朋友,两人正联机在打 BOSS。他们因为太怕痛了所以全点了防御力。弥明、白茶的防御力分别是 a,b ,并且他们拥有一项团队技能,可以将 BOSS 的每次攻击分摊到两人身上。假设这次攻击的攻击力为 k,且已知 BOSS 的攻击破防指数为 p ,那么该技能可以将 k 分摊为两个实数 x,y,满足 x+y=k (注:x,y 可以是负数),使得 BOSS 对弥明和白茶分别造成 \sqrt{p-a+x^2},\sqrt{p-b+y^2} 的伤害
弥明希望 BOSS 的每次攻击对两人造成的伤害总和最少,求这样的分摊方案
输入
首先输入一行三个整数 p,a,b\ (0\le p,a,b\le10^9, a\le p, b\le p, ab > 0)
接下来输入一行一个整数 t(1\le t\le10^5),代表 BOSS 会进行 t 次攻击
接下来输入 t 行,每行一个实数 k(0 < k\le10^9),代表 BOSS 该次攻击的攻击力
输入保证有解且答案唯一,保证输入的小数的小数位均不超过六位
输出
输出 t 行,每行两个实数 x,y,表示使得对弥明和白茶造成的伤害总和最少的 x,y
你的答案被认为是正确的当且仅当你的答案与标准答案的相对误差、绝对误差其一不超过 10^{-2} ,即设你的答案为 r ,标准答案为 r' ,当且仅当满足 \dfrac{|r-r'|}{\max(1,r')}\le10^{-2} 时你的答案视为正确
样例
标准输入 复制文本 |
10 8 5 2 11.0 58.3 |
标准输出 复制文本 |
4.261685 6.738315 22.586929 35.713071 |
提示
提示1:如果你样例可以通过但答案错误,请尝试提高精度,如部分变量的计算可精确到小数点后十二位
提示2:本题灵感来自 这个视频 ,观看这个视频也许不能帮你解出题目,但也许能给你带来快乐;希望能启发你往几何上去思考问题 QwQ
提示3:建议请不要使用微分法或蒙特卡罗法枚举,精度不够,枚举次数过多,容易造成超时
提示4:如果你确信你的时间复杂度是正确的,但仍超时,请尝试使用较为快速的读入方法,如关闭同步流、使用 scanf, printf
乃至快读快写
提示5:可以通过的解法有多种,包括但不限于三分法 , 数学推理, 爬山算法 ;如果你不会这些算法,可以点击链接现学 >_<
提示6:如果你的三分法或爬山算法超时,且你认为你的复杂度正确,请尝试减少精度或特判 a=0 / b=0
提示7:如果你使用数学推理法,样例通过但答案错误,请尝试不要分母有理化或改变计算顺序,以减小精度误差
提示8:推荐输出的答案保留六位小数
来源
wintercode