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 閱讀(549)
評論(0) 編輯 收藏 引用