pku 3301 texas trip 最小正方形覆盖
最小矩形覆盖有个良好的性质,就是最小矩形必定至少一条边上有两个点,这样就可以很方便的枚举,
但我没有看到最小正方形的类似的性质
这样的话连枚举的算法都很困难
标程的算法是枚举转角,先将[0, PI/2]等分1000份,选个最大的,再将这附近的角度等分1000份,其他的就舍弃了,然后迭代下去,这样做应该是有风险的,但cas最多只有30个点,等分的单位角度够小的话,正确率还是很高的
关键是没有更好的枚举方法,我们只能枚举连续的转角,但实际上我们不能枚举连续的东西,只能迭代逼近,这里面也可能发生错误
1 waterloo标程
2 #include <stdio.h>
3 #include <math.h>
4 #include <assert.h>
5
6 #define N 1000
7
8 double x[100], y[100], xx, yy, base,scale;
9 int rep,n,i,j,k,T;
10
11 main(){
12 double minx, maxx, miny, maxy, dx, dy, dd, best; int besti;
13 scanf("%d\n",&T);
14 while (T--) {
15 assert (1 == scanf("%d",&n));
16 for (i=0;i<n;i++) scanf("%lf%lf",&x[i],&y[i]);
17 best = 1000;
18 base = 0; scale=1;
19 for (rep=0;rep<10;rep++) {
20 besti = 0;
21 for (i=0;i<N;i++) {
22 double sininc = sin(base+scale*i*M_PI/2/N);
23 double cosinc = cos(base+scale*i*M_PI/2/N);
24 maxx = maxy = -1e99; minx = miny = 1e99;
25 for (j=0;j<n;j++){
26 xx = cosinc*x[j] - sininc*y[j];
27 yy = sininc*x[j] + cosinc*y[j];
28 //printf("x y xx yy %lg %lg %lg %lg\n",x[j],y[j],xx,yy);
29 if (xx < minx) minx = xx;
30 if (xx > maxx) maxx = xx;
31 if (yy < miny) miny = yy;
32 if (yy > maxy) maxy = yy;
33 }
34 dx = maxx - minx;
35 dy = maxy - miny;
36 dd = dx;
37 if (dy > dd) dd = dy;
38 if (dd < best) {
39 best = dd;
40 besti = i;
41 }
42 //printf("i %d dd %0.5lf\n",i,dd);
43 }
44 base += scale*(besti-1)*M_PI/2/N;
45 scale = scale/N*2;
46 }
47 printf("%0.2lf\n",best*best);
48 }
49 assert(1 != scanf(" %c",&i));
50 }
51
posted on 2009-02-28 16:56
wangzhihao 阅读(499)
评论(0) 编辑 收藏 引用