分类：概率算法

题意：

给出n个点，求出到最近的 给出点 距离最长的点的坐标。

可以通过模拟退火来实现：

先随机出一个点A，再在以A为圆心，以R为半径，随机出一个点B。若ans(B)>ans(A),则用B来更新A。若ans(B)<ans(A)，则以一定的概率P(dE) = exp( dE/T )来更新A，其中exp为自然指数，T是一个自己定的数，dE是ans(B)>ans(A)。

在每次随机点B后，R、T都要适当的减小，以便缩小随机范围和结束求解。

简单来说，模拟退火就是以一定的概率接受一个不是最优的解，来跳出之前的最优解，避免把局部最优解当成全局最优解

最后要注意常数T，和随机范围R的选取

继续阅读3167逃离陷阱

模拟退火。

概念见大白话解析模拟退火算法。

实现：

首先随机在平面中取一个点 A，每轮都以这个点为圆心，R 为半径（每轮递减）随机选取若干个圆上的点 B。若点 B 已经优于 A，则直接用 B 更新 A，否则以一个概率 P（每轮递减）决定是否以 B 更新 A。这样就可以得到一个近似最优解。

在实现过程中，可以同时维护 20 个点，最后取这些点中的最优值作为答案。具体 R 与 P 的初始值与更新方式见代码。

代码如下：

继续阅读[POJ 1379] [CEOI 1999] 逃离陷阱