首页 > 代码库 > HDU 5017 Ellipsoid(模拟退火)

HDU 5017 Ellipsoid(模拟退火)

2024-07-23 23:34:06   227人阅读

Ellipsoid

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1015    Accepted Submission(s): 359
Special Judge

Problem Description
Given a 3-dimension ellipsoid(椭球面)

your task is to find the minimal distance between the original point (0,0,0) and points on the ellipsoid. The distance between two points (x1,y1,z1) and (x2,y2,z2) is defined as 
 

Input
There are multiple test cases. Please process till EOF.

For each testcase, one line contains 6 real number a,b,c(0 < a,b,c,< 1),d,e,f(0 ≤ d,e,f < 1), as described above. It is guaranteed that the input data forms a ellipsoid. All numbers are fit in double.
 

Output
For each test contains one line. Describes the minimal distance. Answer will be considered as correct if their absolute error is less than 10-5.
 

Sample Input
1 0.04 0.01 0 0 0
 

Sample Output
1.0000000
 
题意：找到椭球面上的点距离远点最近的点。
思路：模拟退火搜索x,y,然后求出z,再算距离。模拟退火能AC感觉就是看出题人的数据。。。初始步长最好定的小一点，退货速度慢一点。。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
#define REP(_,a,b) for(int _ = (a); _ <= (b); _++)
const double eps = 1e-10;
const double P = 0.99;//退火速度
const int dirX[9] = {0,1,-1,1,-1,0,0,1,-1};
const int dirY[9] = {0,1,-1,-1,1,1,-1,0,0};
double a,b,c,d,e,f;
int dcmp(double x) {
    if(fabs(x) < eps) return 0;
    else if(x < 0) return -1;
    else return 1;
}
bool getRoot(double a,double b,double c,double &x1) {
    double delta = b*b-4*a*c;
    if(dcmp(delta) < 0) return false;
    x1 = (-b+sqrt(delta))/(a*2);
    return  true;
}
void solve() {

    double step = 0.1;
    double x = 0, y = 0;
    double ans = 1/c;
    while(step > eps) {
        int dir = 0;
        REP(i,1,8) {
            double xx = x + step*dirX[i]*1.0;
            double yy = y + step*dirY[i]*1.0;
            double zz;
            if(getRoot(c,d*yy+e*xx,a*xx*xx+b*yy*yy+f*xx*yy-1,zz)) {
                if(xx*xx+yy*yy+zz*zz < ans) {
                    dir = i;
                    ans = xx*xx+yy*yy+zz*zz;
                }
            }
        }
        if(dir != 0) {
            x += step*dirX[dir];
            y += step*dirY[dir];
        }
        step *= P;
    }
    printf("%.8lf\n",sqrt(ans));
}
int main(){

    while(~scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)) {
        solve();
    }
    return 0;
}


HDU 5017 Ellipsoid(模拟退火)


联系
我们