POJ 1379 模拟退火

  1 #include <iostream>
  2 #include <fstream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <string>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <queue>
 11 #include <stack>
 12 #include <vector>
 13 #include <set>
 14 #include <map>
 15 #include <list>
 16 #include <iomanip>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <bitset>
 20 #include <ctime>
 21 
 22 using namespace std;
 23 
 24 #define pau system("pause")
 25 #define ll long long
 26 #define pii pair<int, int>
 27 #define pb push_back
 28 #define pli pair<ll, int>
 29 #define pil pair<int, ll>
 30 #define clr(a, x) memset(a, x, sizeof(a))
 31 
 32 const double pi = acos(-1.0);
 33 const int INF = 0x3f3f3f3f;
 34 const int MOD = 1e9 + 7;
 35 const double EPS = 1e-9;
 36 
 37 /*
 38 #include <ext/pb_ds/assoc_container.hpp>
 39 #include <ext/pb_ds/tree_policy.hpp>
 40 using namespace __gnu_pbds;
 41 #define TREE tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update>
 42 TREE T;
 43 */
 44 
 45 int T, n;
 46 struct Point {
 47     double x, y;
 48     Point () {}
 49     Point (double x, double y) : x(x), y(y) {}
 50     double dis(Point p) {
 51         return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
 52     }
 53 } p[1005];
 54 inline double get_p(double delta, double T) {
 55     return exp(delta / T);
 56 }
 57 double cal(Point pp) {
 58     double res = 1e18;
 59     for (int i = 1; i <= n; ++i) {
 60         double tres = pp.dis(p[i]);
 61         res = min(res, tres);
 62     }
 63     return res;
 64 }
 65 const int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
 66 double X, Y;
 67 Point ans_p;
 68 double tuihuo() {
 69     double x = rand() % (int)(X + 1), y = rand() % (int)(Y + 1);
 70     double res = cal(Point(x, y)), ans = res;
 71     ans_p = Point(x, y);
 72     double T = 10000 / min(X, Y), phi = 0.999;
 73     for (int rep = 1; rep <= 100000; ++rep) {
 74         int r = rand() % 4;
 75         int deltax = dir[r][0], deltay = dir[r][1];
 76         double tox = x + deltax * T * X;
 77         double toy = y + deltay * T * Y;
 78         if (0 <= tox && tox <= X && 0 <= toy && toy <= Y) {
 79             double tres = cal(Point(tox, toy));
 80             if (tres > res) {
 81                 x = tox, y = toy;
 82                 res = tres;
 83                 if (res > ans) {
 84                     ans = res;
 85                     ans_p = Point(x, y);
 86                 }
 87             } else {
 88                 double delta = tres - res;
 89                 double prob = get_p(delta, T);
 90                 prob = max(0.1, prob);
 91                 if (rand() < prob * RAND_MAX) {
 92                     x = tox, y = toy;
 93                     res = tres;
 94                 }
 95             }
 96         }
 97         T *= phi;
 98     }
 99     return ans;
100 }
101 int main() {
102     srand(19980305);
103     scanf("%d", &T);
104     while (T--) {
105         scanf("%lf%lf%d", &X, &Y, &n);
106         for (int i = 1; i <= n; ++i) {
107             scanf("%lf%lf", &p[i].x, &p[i].y);
108         }
109         tuihuo();
110         printf("The safest point is (%.1f, %.1f).\n", ans_p.x, ans_p.y);
111     }
112     return 0;
113 }