不同于模拟退火的一种优化算法

我本来一看到这道题就打了个模拟退火，但是死活模拟不对，样例死活过完就是重心。

翻题解发现可以用向四周的步长移动来求出最优解。不知道这叫什么名字但肯定不是模拟退火。

算法的思想是这样的：

给出4个方向上下左右，然后初始化步长，如果当前新答案比老答案好就更新这个答案，否则步长变短一半。步长变为0停止。

算出来的就是答案。。。

代码：

#include
    
     #include
     
      #include
      
       const double eps = 1e-6;const int dx[] = {0, 1, -1, 0, 0};const int dy[] = {0, 0, 0, 1, -1};struct Circle{    int x, y, r;} cir[4];double ansx, ansy, ans;double dist(double x, double y, double xx, double yy){    return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));}double cal(double x, double y){    double res = 0;    double g[4];    for(int i = 1; i <= 3; i++) g[i] = dist(x, y, cir[i].x, cir[i].y) / cir[i].r;    res += (g[1] - g[2]) * (g[1] - g[2]);    res += (g[2] - g[3]) * (g[2] - g[3]);    res += (g[3] - g[1]) * (g[3] - g[1]);    return res / 3;}int main(){    srand(19260817);    for(int i = 1; i <= 3; i++) scanf("%d%d%d", &cir[i].x, &cir[i].y, &cir[i].r);    ansx = (cir[1].x + cir[2].x + cir[3].x) / 3.0;    ansy = (cir[1].y + cir[2].y + cir[3].y) / 3.0;    ans = cal(ansx, ansy);    double T = 1;    while(T > eps)    {        int dir = -1;        for(int i = 1; i <= 4; i++)        {            double res = cal(ansx + dx[i] * T, ansy + dy[i] * T);            if(res < ans) ans = res, dir = i;        }        if(dir == -1) T /= 2;        else ansx += dx[dir] * T, ansy += dy[dir] * T;    }    if(ans < eps) printf("%.5lf %.5lf\n", ansx, ansy);    return 0;}