Posted on 2010-11-28 22:07
小小菜鸟蛋 阅读(290)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://poj.org/problem?id=1379
题目大意：
在一个给定长宽的矩形中，已知有n个地雷，现在要求出矩形内一个点，使该点到其最近的地雷的距离最远，且没有其他点到其最近地雷的距离会比该点的大。
解析：
此题按照"pku_3285 Point of view in Flatland"讲的那样模拟退火，只是因为可能会出现在地雷成堆聚集，然后几个堆有相隔很远的情况，这样单一退火很容易导致WA，所以采用多组初始解并行退火，最后求这几组解的最优解。
源代码如下：（来自duolon）
01 #include <cstdio>
02 #include <cmath>
03 #include <ctime>
04 #include <cstdlib>
05 #include <algorithm>
06 using namespace std;
07
08 const int N = 1050;
09 const int M = 30;
10 const int L = 30;
11 const double eps = 1e-3;
12 struct Point
13 {
14 double x, y, d;
15 };
16 Point p[N];
17 int n;
18 int X, Y;
19 Point s[M];
20
21 double sqr(double x)
22 {
23 return x * x;
24 }
25
26 double dis(int idx)
27 {
28 if (s[idx].x < 0 || s[idx].x > X) return 0;
29 if (s[idx].y < 0 || s[idx].y > Y) return 0;
30 double ret = 1e10;
31 for (int i = 1; i <= n; i++)
32 ret = min(ret, sqr(s[idx].x - p[i].x) + sqr(s[idx].y - p[i].y));
33 return ret;
34 }
35
36 void work()
37 {
38 scanf("%d%d%d", &X, &Y, &n);
39 for (int i = 1; i <= n; i++)
40 scanf("%lf%lf", &p[i].x, &p[i].y);
41 for (int i = 1; i < M; i++)
42 {
43 s[i].x = rand() % (X+1);
44 s[i].y = rand() % (Y+1);
45 s[i].d = dis(i);
46 }
47 for (double delta = max(X, Y); delta > eps; delta *= 0.88)
48 for (int i = 1; i < M; i++)
49 for (int j = 1; j <= L; j++)
50 {
51 double phi = rand();
52 s[0].x = s[i].x + delta * cos(phi);
53 s[0].y = s[i].y + delta * sin(phi);
54 if ((s[0].d = dis(0)) > s[i].d)
55 s[i] = s[0];
56 }
57 int idx = 1;
58 for (int i = 1; i < M; i++)
59 if (s[i].d > s[idx].d)
60 idx = i;
61 printf("The safest point is (%.1f, %.1f).\n", s[idx].x, s[idx].y);
62 }
63
64 int main()
65 {
66 int T;
67 scanf("%d", &T);
68 while (T--)
69 work();
70 }
注意：
1、srand(time(NULL)); 不能用这个来初始化随机种子，pku上禁止time(NULL)，会返回runtime error。若要用srand，则srand（100）这样随便写个int进去就可以。
2、vs c++里的rand()返回 [0,2^16)的整数；gcc里rand()返回 [0,2^32)的整数。
要获得[0,1)的实数，必须写 rand() / RAND_MAX，其中RAND_MAX是定义在cstdlib头文件里的一个返回最大随机值的常量。
3、标准规定，浮点输出全都要用%f，如果是%lf 则会WA~~呃，需要提醒的是，double输入是%lf，输出是%f ；float则都是%f 。