hdu 5017 模拟退火/三分求椭圆上离圆心最近的点的距离

http://acm.hdu.edu.cn/showproblem.php?pid=5017

求椭圆上离圆心最近的点的距离。

模拟退火和三分套三分都能解决

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const double eps = 1e-8;
const double r = 0.99;  //降温速度
const int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
const int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
double a, b, c, d, e, f;

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

//已知x,y,求z
double getz(double x, double y) {
    double A = c, B = e * x + d * y,
        C = a * x * x + b * y * y + f * x * y - 1;
    double delta = B * B - 4 * A * C;
    if (delta < 0) return 1e60;
    double z1 = (-B + sqrt(delta)) / 2 / A,
        z2 = (-B - sqrt(delta)) / 2 / A;
    if (z1 * z1 < z2 * z2) return z1;
    else return z2;
}

double solve() {
    //模拟退火
    double step = 1;    //步长
    double x = 0, y = 0, z;
    while (step > eps) {
        z = getz(x, y);
        for (int i = 0; i < 8; i++) {
            double nx = x + dx[i] * step,
                ny = y + dy[i] * step,
                nz = getz(nx, ny);
            if (nz > 1e30) continue;
            if (dis(nx, ny, nz) < dis(x, y, z)) {
                x = nx; y = ny; z = nz;
            }
        }
        step *= r;
    }
    return dis(x, y, z);
}

int main() {
    while (scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f) != EOF) {
        printf("%.8f
", solve());
    }
    return 0;
}

三分要比退火快

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
const double INF = 10000;
const double eps = 1e-8;
double solve(double a,double b,double c)
{
    double delta = b*b-4.0*a*c;
    if(delta < eps)
        return INF;
    return (sqrt(delta)-b)/(a*2.0);
}
double a,b,c,d,e,f;
double z(double x,double y)
{
    double zz = solve(c,d*y+e*x,a*x*x+b*y*y+f*x*y-1);
    return x*x+y*y+zz*zz;
}
double y(double x)
{
    double l = -INF,r = INF;
    int t = 200;
    while(l+eps<r){
        double mid = (l+r)/2,rr = (mid+r)/2;
        if(z(x,rr) < z(x,mid))
            l = mid;
        else
            r = rr;
    }
    return z(x,l);
}
double x()
{
    double l = -INF,r = INF;
    int t = 200;
    while(l+eps<r){
        double mid = (l+r)/2,rr = (mid+r)/2;
        if(y(rr) < y(mid))
            l = mid;
        else
            r = rr;
    }
    return sqrt(y(l));
}
int main(){
    while(~scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f))
        printf("%.8lf
",x());
    return 0;
 }