首页 > 其他 > 详细

HDU 5017 Ellipsoid(模拟退火)

时间:2014-09-23 15:18:05      阅读:212      评论:0      收藏:0      [点我收藏+]

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(椭球面)
bubuko.com,布布扣

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 bubuko.com,布布扣
 

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(模拟退火)

原文:http://blog.csdn.net/mowayao/article/details/39498805

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!