Posted on 2008-09-01 17:55
Hero 阅读(217)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 //PKU 3122 Accepted 452K 32MS G++ 1661B
2
3 //二分
4 //奇怪--变成整型去做就不对
5
6 #include <stdio.h>
7 #include <string.h>
8 #include <stdlib.h>
9 #include <math.h>
10
11 const double PI = 2.0 * acos( 0.0 ) ;
12 //const double PI = acos( -1.0 ) ;
13
14 const int deg = 1000000 ;
15 const int size = 11000 ;
16
17 int radii[size] ;
18 double area[size] ;
19 double maxarea ;
20
21 int innum ;
22 int inn, inf ;
23
24 void input()
25 {
26 scanf( "%d %d", &inn, &inf ) ; maxarea = -1.0 ;
27 for( int i=1; i<=inn; i++ )
28 {
29 scanf( "%d", &radii[i] ) ;
30 area[i] = PI * radii[i] * radii[i] ;
31 if( maxarea < area[i] ) maxarea = area[i] ;
32 }
33 }
34
35 int test( int mid )
36 {
37 double cutarea = mid * 1.0 / deg ; int cnt = 0 ; double tarea ;
38
39 for( int i=1; i<=inn; i++ )
40 {
41 //tarea = area[i] ;
42 //while( tarea - cutarea > 0 ) { tarea -= cutarea ; cnt++ ; }
43 cnt += area[i] / cutarea ;
44 }
45
46 return cnt ;
47 }
48
49 void process()
50 {
51 int left = 0 ; int right = (int)(maxarea*deg)+100 ; int mid ;
52
53 while( left + 1 < right )
54 {
55 mid = (left+right)>>1 ;
56 if( test(mid) > inf ) left = mid ;
57 else right = mid ;
58 }
59
60 double out = right *1.0 / deg ;
61
62 printf( "%lf\n", out ) ;
63 }
64
65 int test1( double mid )
66 {
67 int cnt = 0 ;
68 for( int i=1; i<=inn; i++ )
69 {
70 cnt += (int)(area[i]/mid) ;
71 }
72
73 return cnt ;
74 }
75
76 void process1()
77 {
78 double left = 0 ; double right = maxarea ; double mid ;
79
80 while( fabs(left-right) > 0.000005 )
81 {
82 mid = (left + right) / 2 ;
83 if( test1( mid ) > inf ) left = mid ;
84 else right = mid ;
85 }
86
87 printf( "%lf\n", mid ) ;
88 }
89
90 int main()
91 {
92 //freopen( "in.txt", "r", stdin ) ;
93
94 while( scanf( "%d", &innum ) != EOF )
95 {
96 for( int ct=1; ct<=innum; ct++ )
97 {
98 input() ;
99
100 process1() ;
101
102 //output() ;
103 }
104 }
105
106 return 0 ;
107 }