BZOJ 3680: 吊打XXX (广义费马点,模拟退火+爬山)

3680: 吊打XXX

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 2043  Solved: 732
[Submit][Status][Discuss]

Description

gty又虐了一场比赛,被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身,但还是被人多势众的蒟蒻抓住了。蒟蒻们将
n个gty吊在n根绳子上,每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同,绳
结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标,由于他太弱了决定向你求助。
不计摩擦,不计能量损失,由于gty足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n(1<=n<=10000),表示gty的数目。
接下来n行,每行三个整数xi,yi,wi,表示第i个gty的横坐标,纵坐标和重力。
对于20%的数据,gty排列成一条直线。
对于50%的数据,1<=n<=1000。
对于100%的数据,1<=n<=10000,-100000<=xi,yi<=100000

Output

输出1行两个浮点数(保留到小数点后3位),表示最终x的横、纵坐标。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000

HINT

Source


By wangxz

思路:

看起来是物理题。。其实就是求广义非费马点。。

也就是带权费马点。

一般的费马点是说,所有点到这个点的距离之和最小。

带权的费马点就是每个点到这个点的距离*权值,和最小。

这道题用到的才是真正的模拟退火!

模拟退火很重要的一部分就是允许有一定概率向不优的方向走,之前写的所谓的“模拟退火”的题目,全都没有体现这一点。

所以那些,其实就是一个爬山法吧。。

而且看到主席如是说…

webwxgetmsgimg

 

 

这道题真的很棒。

初始搜索范围很大的时候用模拟退火,快速得到一个大致范围。

但是由于精度不能很好的保证,于是在做完模拟退火后在答案附近爬山。

完美的分段思想!

一直调不对样例的原因是。。。

忘记把ans初始化成最大值23333

 

hdu 5017 Ellipsoid (模拟退火,计算椭球到定点的最小距离)

 

hdu 5017 题目链接

题意:给出椭球方程的6的参数 a,b,c,d,e,f 

问椭球上的点到原点(0,0,,0)的最小距离是多少。

思路:感觉难点在于,如何保证搜到的点一直在椭球上。

一开始我考虑到了用椭球的参数方程。。。。然后发现不记得是什么了2333

然后看了题解,发现比较巧妙的做法是,只搜索x,y,然后从椭球方程中解出z。

x,y确定以后,椭球方程就变成了一个关于z的一元二次方程,可解。

由于是要求距离原点的最小距离,而现在可能得到的两个解是关于xoy平面对称的,只有z坐标不同,因此我们取距离原点近的那个z。

以及,感觉在平面上搜4个方向就好。。。没必要8个方向。。?

2016-08-31 14-49-34 的屏幕截图

wa到死是因为。。。计算距离。。忘记开根号。。。。。呵呵呵呵呵呵呵呵呵我是傻逼。。。

poj 2069 Super Star (模拟退火)

poj 2069 题目链接

题意:给出n个点,找出包含这n个点的最小半径的外接球。求球的半径。

思路:模拟退火。不过在走的时候,不是随机上下左右前后6个方向走,而是每次往距离当前球心最远的点的方向走。这样才能通过(随机6个方向的写法样例也是可以通过的)

所以模拟退火的精髓大概是“概率减小” 而不是“随机”?

以及,我看到的资料中,对于模拟退火的介绍,都有一部分是“允许一定概率向着不优的方向移动,但是这个概率会越来越小(因此叫退火)”

但是做了几道所谓的“模拟退火”的题目,发现并没有这部分。。。?

那样的话应该是爬山法?

以及看到说模拟退火适合并行计算。。。

是不是体现在我可以放k个初始解,然后每次最优的答案是在k个答案中取最优?

 

 

 

poj 2420 A Star not a Tree? (模拟退火模板题求多边形费马点)

poj 2420

题意:求多边形费马点,也就是距离所有点的距离之和最小的点。

思路:模拟退火裸题。

关于模拟退火的学习:
模拟退火讲解

我就记住了一句话2333:

爬山算法:兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法,它不能保证局部最优值就是全局最优值。

  模拟退火:兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。

等写一波题再来总结

以及:感觉适牛的版好简洁嘿嘿嘿。

 

poj 1379 Run Away (模拟退火)

poj 1379题目链接

题意:给出一个矩形区域的长宽,给出区域中若干点,问距离所有点的最近距离的最大值是多少。

思路:很容易想到模拟退火。

比赛的时候因为忘记判断矩形边界导致答案错得离谱2333

加上之后1A