/ Vijos / 题库 /

等离子态加速器

等离子态加速器

背景

在这一系列中,你将化身为Lwins。(至于人设什么的有空再说...)
Softstar原来是一名格斗家,后来由于被Trin发现在物理学和化学上有惊人天赋,从而转行为科学家(虽然跨度很大,但是确实成功了,顺带一提,Softstar也成功减肥100斤)。

Softstar最近在做的项目 - X2-等离子态加速器的研制出现了突破性进展。不过仍然有一些问题。他想到了善于思考,在理论魔法学界中占有首要地位的Trin,于是找到了他,请他加入研制(当然,首要的还是先解决这个问题)。

与此同时,Uff在灵渊遇到了一些问题,他是5个伙伴中最不善于思考的人。(当然也是最强悍的剑士)于是他给Trin发了一条消息,请求他的援助,不过收到回信后他失望了......
目光再转移回来,Softstar正准备乘坐飞艇到Trin的家中......

描述

Softstar当然不是吃素的,他在将问题给Trin之前已经作了充分研究并简化成一个数学模型(其中大部分工作是在开飞艇的同时,一心二用而完成的,由此足见这位科学家的强大),以下是他关于此问题的描述:
在平面上有n个点Pi(xi,yi),对每一个点Pi(xi,yi),作过它的直线x=xi,现在要找一条直线y=ax+b,这条直线和x=xi(1≤i≤n)的交点记作Ai,Ai到Pi的距离记作wi,这条直线要满足的条件是:在所有直线中,这条直线所确定的所有wi的平方和最小(先平方再求和)
但是Softstar找到Trin后,发现这个任务根本不可能托付给他,因为Trin正在进行负能量和魔法物质的研究(Uff的请求援助当然是因此遭拒,关于这个问题我们下次再说),Softstar深知Trin一开始研究关于魔法的问题就会没完没了,所以他找到了乐于助人的你,恳请你帮助他解决这个问题。

P.s. 简要叙述一下你的身份:你是一名隐居数学家(当然远不止如此),和Softstar,Trin,Uff,Void有千丝万缕的联系。

格式

输入格式

第一行为一个整数n。(n≤100000)
接下来n行为xi,yi,其为正实数。(0≤xi,yi≤100000)

输出格式

a和b,保留一位小数。(见题目叙述)
对使用pascal的同学的提示:pascal在对如-0.01这样的数保留一位小数时会变成-0.0,在输出中应改为0.0。

20%的数据满足n≤10
30%的数据满足n≤100
50%的数据满足n≤1000
80%的数据满足n≤10000
100%的数据满足n≤100000

样例1

样例输入1

3
1.0 5.0
3.0 15.0
5.000 25.000

样例输出1

5.0 0.0

限制

1s

提示

[关于样例]
显然,这3个点在同一直线上,当直线的解析式为y=5x时,直线刚好过这三点,因此w1^2+w2^2+w3^2=0,是为最小值。

[算法提示]
1.算法不止一种,下面是某种算法的提示,当然,这不代表其是最简单的算法。

2.F(x,y)在(x0,y0)取得极值的必要条件是当x=x0,y=y0时,∂F/∂x=0且∂F/∂y=0。

来源

鱼丸原创

信息

ID
1672
难度
6
分类
计算几何 | 几何知识 点击显示
标签
递交数
224
已通过
60
通过率
27%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库