/ Vijos / 题库 /

一出碎月斩

一出碎月斩

背景

Uff是一位剑士,他不太喜欢像Trin似的在战斗中在脑子中开辟出一个分析战场情况的区域(注:Trin(即出题者)不是计算机)来辅助自己赢得战斗。与之相反,Uff更倾向于跟随自己的自由意志与别人战斗。(由于Uff的实力不俗,从他开始使用这种"恶心"的战斗方式以来从未输过(注:"恶心"这个词出自Trin))这次他来灵渊解决异变(关于异变的问题我们可以从容地留到下次讨论),却碰上了捷足先登的同样来解决异变的魔法工会的人。Uff当然不会甘心(大老远飞过来,换成我我也不干),他想到了在工会中有极高声望的Trin,于是立即给他发了一封消息。但是当他接到回信后彻底OTZ了...我们可以来看看当时Trin的回信:
"今天的天气真好,啊!"
Uff知道他收到这样的回信的可能原因有三个:一、Trin发抽;二、Trin在进行有关魔法的工作;三、Trin的通讯器又被他的小弟弟拿去玩儿了。

无论出自哪个原因,Uff自知请求Trin的帮助无望,于是只好准备暴力解决。

事实上魔法工会的人早已进入灵渊,而Uff还在灵渊入口,那么为什么他会知道魔法工会的人在他之前到达这里了呢?这一切都是因为魔法工会的人所布置的圆形的结界阵。

这个圆形的结界阵是正对着Uff的,Uff试着使用他的得意技 - "一出碎月斩"来砍断结界,他使用了最大了力量,这时候他是竖直出刀的,一声惊天动地的巨响后...很遗憾,他没有成功。

想必现在大家对Uff的性格也有所了解了,他自然不会因此放弃,于是他想到了你,他知道由你来解决这个问题是再好不过的了。你当然愿意帮助他,于是开始了你的计算。

首先,你把这个结界置于二维空间中,根据对这种圆形结界的了解,你判断出Uff的"一出碎月斩"(注意,剑划过的路径是直线)能强行斩断它的充分必要条件是:
一、剑划过的路径必须经过结界中心点
二、Uff使出这一技能时在剑身中注入的力量,加上斩击原本的力量,如果按照剑划过的路径依然小于结界的阻力,则无法斩断。(注:在某点的阻力与此点密度成正比)
根据上面的分析,你已经有了帮他解决这个问题思路:
一、弄清楚这个结界的大小以及它的各部分的密度
二、找出一条过圆心的路径,使得剑划过这条路径能斩断的力量临界值(力量临界值的意义即刚好能使剑沿着此路径斩断此结界所需要的力量)比其他路径的都小。

三、告诉他这个力量值,如果他的力量比这小..那么就很遗憾了。

现在便是要实行你的计划,事实上只有第二步有一些困难,这也正是你要做的。

描述

现在,把这个结界阵看作一个圆心为原点,半径为r的圆形。这个结界的各部分密度都不同。

你注意到,Uff的技能对于任何圆形结界,剑划过的路径必须经过圆心。

首先你考虑,如果这个结界是最简单的圆形结界 - 纯魔法结界(魔法初学者必修),这个结界的特性是:各部分密度相同,设其为p0。那么显然,无论Uff按照哪条过圆心的直线路径使用技能斩断它,都至少需要g*2r*p0的力量(g是你设置的常数,它的意义是:g单位的力量可以斩断1单位密度为p的结界,经过你的计算,g=1.0027028...,为方便你的计算,在这个问题中你设g=1)。

事实当然没有这么简单,(上面的例子是为了说明力量与密度的大致关系而写)经过你的研究,你发现这个结界是高级圆形结界 - Graphics ThomasX结界,这个结界的特点是它允许用多人的复合魔法共同设置。(你的另一个疑问 - "这个结界所需魔法能量这么高,而除了Trin外尚无人能达到这种程度"也随之解决)现在我们就来详细研究这个结界:
这个结界是圆形结界,你用了与上面相同的办法研究它:把它置于二维平面中,令它的圆心和原点重合,设半径为r。

这个结界有一个特性:因为它是由多人联合布置的(设为n人),设第i人(1≤i≤n)在点(x0,y0)布置的密度为pi(x0,y0),那么所以实际上,这个结界在这个点p(x0,y0)的密度满足:
p(x0,y0)=sigma(pi(x0,y0)) (i从1取到n)
而每个人的布置方式都是:
(设此人为第i个人,ki,di为常数)
在结界中设置一个魔法聚合点Ai(xi,yi),在这个点增加密度pi(xi,yi)=ki,而结界中除此点外增加的密度pi(x,y)=ki-di*((x-xi)^2+(y-yi)^2)。

显然从几何上来理解,可以认为每个人都布置了一个简单高级结界 - Graphics ThomasA结界,它的特征是:一、结界形状为圆形,二、结界有一魔法聚合点,此点密度最高,而"其他点到魔法聚合点的距离的平方"和"其他点的密度和魔法聚合点的密度的差"成正比例关系。最终的结界即n个人设置的Graphics ThomasA结界的线性叠加。现在要找一条过圆心的直线,使得它满足题目背景所要求的条件,然后告诉Uff这个力量值。

格式

输入格式

第1行为一个整数n (n≤1000)
第2行为一个正实数r (0<r≤100)
下面n行:ki,di,xi,yi (|ki|,|di|,|xi|,|yi|≤100)

输出格式

最小力量值,保留2位小数。

样例1

样例输入1

1
1.0
0.0 0.0 0.0 0.0

样例输出1

0.00

限制

1s

提示

如果你认真看了题目且真的会做这道题的话,你一定能理解下面这句话的含义:
“Uff绝不可能斩断这个结界。”
请各位加油吧!

信息

ID
1674
难度
8
分类
计算几何 | 几何知识 点击显示
标签
递交数
64
已通过
7
通过率
11%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库