HDU 5017 – Ellipsoid [几何+模拟退火]

点击打开HDU题目链接

题意:给一个椭球的一般式方程,然后求原点到球上一点的最短距离。

分析:模拟退火逐步取得最优值,三分套二分之类的可能会退公式麻烦一些。下面是跟网上学的模拟退火算法做的。

#include <bits/stdc++.h>
using namespace std;

const double inf = 1e8, eps = 1e-8;
const int dir[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
double a, b, c, d, e, f;

inline double dis(double x, double y, double z) {
    return sqrt(x * x + y * y + z * z);
}

double calcz(double x, double y) {
    double A = c, B = d*y + e*x, C = a*x*x + b*y*y + f*x*y - 1.0;
    double det = B * B - 4.0 * A * C;
    if(det < 0.0) return inf + 7.0;
    double z1 = ((-B)+sqrt(det))/(2.0*A), z2 = ((-B)-sqrt(det))/(2.0*A);
    if(dis(x, y, z1) > dis(x, y, z2))
        return z2;
    return z1;
}

int main() {
    while(~scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f)) {
        double x = 0.0, y = 0.0, z = sqrt(1.0/c);
        double step = 1.0, rate = 0.97;
        while(step > eps) {
            for(int i = 0; i < 8; ++i) {
                double xx = x + step * dir[i][0], yy = y + step * dir[i][1];
                double zz = calcz(xx, yy);
                if(zz > inf) continue;
                if(dis(xx, yy, zz) < dis(x, y, z))
                    x = xx, y = yy, z = zz;
            }
            step *= rate;
        }
        printf("%.7lf\n", dis(x, y, z));
    }
    return 0;
}

欢迎留言