HDU - 5017 Ellipsoid（模拟退火）

题意

给一个三维椭球面，求球面上距离原点最近的点。输出这个距离。

题解

模拟退火。

把\(z = f(x, y)\)函数写出来，这样通过随机抖动\(x\)和\(y\)坐标就能求出\(z\)。

代码

//#include <bits/stdc++.h>

#include <cstdio>

#include <cmath>

#include <ctime>

#include <algorithm>

#include <iostream>

#define FOPI freopen("in.txt", "r", stdin)

#define FOPO freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

const int maxn = 100 + 5;

const double eps = 1e-3;

const int inf = 0x3f3f3f3f;

const double start_T = 10000;

struct Point

{

    double x, y, z;

    Point() {}

    Point(double _x, double _y, double _z):x(_x), y(_y), z(_z) {}

};

double a, b, c, d, e, f;

int dx[] = {1, 1, 1, -1, -1, -1, 0, 0},

    dy[] = {0, 1, -1, 0, 1, -1, -1, 1};

int n;

double dist(Point a)

{

    return sqrt(a.x*a.x + a.y*a.y + a.z*a.z + 1e-8);

}

double getz(double x, double y)

{

    double A = c, B = d*y + e*x, C = a*x*x + b*y*y + f*x*y - 1;

    double delta = B*B - 4*A*C;

    if (delta < -eps) return inf+1;

    double z1 = (-B + sqrt(delta)) / 2 / A,

            z2 = (-B - sqrt(delta)) / 2 / A;

    return dist(Point(x, y, z1)) < dist(Point(x, y, z2)) ? z1 : z2;

}

double SA()

{

    Point p(0, 0, getz(0, 0)), to;

    double ans = dist(p), rate = 0.98, T = start_T;

    while(T > eps)

    {

        double fx, fy, fz;

        double tmp = inf;

        for (int aim = 0; aim < 8; aim++)

        {

            fx = (p.x+1.0*dx[aim]/start_T*T);

            fy = (p.y+1.0*dy[aim]/start_T*T);

            //printf("%f\n", T);

            fz = getz(fx, fy);

            if (fz >= inf) continue;

            double d = dist(Point(fx, fy, fz));

            if (d < tmp)

            {

                tmp = d;

                to = Point(fx, fy, fz);

            }

        }

        if (tmp < ans)

        {

            ans = tmp;

            p = to;

        }

        else if ((rand()%10000)/10000.0 < exp((ans-tmp)/ T * start_T))

        {

            ans = tmp;

            p = to;

        }

        T *= rate;

    }

    return ans;

}

int main()

{

//    FOPI;

    srand(time(NULL));

    while(~scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f))

        printf("%.7f\n", SA());

}