【HDOJ】5017 Ellipsoid

简单地模拟退火。
 1 /* 5017 */
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 
 7 #define INF 1e30
 8 
 9 const double eps = 1e-8;
10 const double next = 0.99;
11 int dir[8][2] = {
12     {-1, 0}, {1, 0}, {0, -1}, {0, 1},
13     {-1, 1}, {-1, -1}, {1, -1}, {1, 1}
14 };
15 double a, b, c, d, e, f;
16 
17 double Length(double x, double y, double z) {
18     return sqrt(x*x + y*y + z*z);
19 }
20 
21 double getZ(double x, double y) {
22     double A, B, C, delta, tmp;
23     double z1, z2;
24     
25     A = c;
26     B = d*y + e*x;
27     C = a*x*x + b*y*y + f*x*y - 1.0;
28     tmp = B*B - 4*A*C;
29     if (tmp < 0)
30         return INF;
31     delta = sqrt(tmp);
32     z1 = (-B+delta)/(2.0*A);
33     z2 = (-B-delta)/(2.0*A);
34     
35     return fabs(z1) < fabs(z2) ? z1:z2;
36 }
37 
38 int main() {
39     double x, y, z;
40     double xx, yy, zz;
41     double step, tmp, ans;
42     int i;
43     
44     #ifndef ONLINE_JUDGE
45         freopen("data.in", "r", stdin);
46         freopen("data.out", "w", stdout);
47     #endif
48     
49     while (scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f) != EOF) {
50         x = 0;
51         y = 0;
52         z = getZ(x, y);
53         ans = Length(x, y, z);
54         step = 1.;
55         while (step > eps) {
56             for (i=0; i<8; ++i) {
57                 xx = x + dir[i][0]*step;
58                 yy = y + dir[i][1]*step;
59                 zz = getZ(xx, yy);
60                 if (zz >= INF)
61                     continue;
62                 tmp = Length(xx, yy, zz);
63                 if (tmp < ans) {
64                     x = xx;
65                     y = yy;
66                     z = zz;
67                     ans = tmp;
68                 }
69             }
70             step *= next;
71         }
72         printf("%.7lf
", ans);
73     }
74     
75     return 0;
76 }