感谢 mengyou 完全是他教我的。
http://acm.jlu.edu.cn/joj/showproblem.php?pid=2346
二分 :首先,这种题目,结果一定在一定的范围内部,一定会找到结果。所以可以应用二分。
二分形成的查找树,貌似叫做线段树。。。嗯,看mengyou搞得时候偶尔问的。
很猛很猛,因为每次砍了一半。。这是多么可怕。。。
有机会一定要把线段树搞明白了。。。。因为实在是太快了。
这里我们查找的是刀口的长度,而是用上下两个部分的面积的比和给的比进行比较,来进行二分查找的。
而上面的面积可以各种约分。。。。
mengyou说过,sin 和 cos 精确度很高。tan尽量不要应用。。
嗯。。。扇形的面积是所占的弧度 与 360度 的比值,所以扇形的面积就是这个比值 * 园的面积(PI * R * R) 也就是
而我们传入的是刀口长度的一半,也就是三角形的 a ,r已知,这样可以求得b sqrt(r * r - a * a)
然后下面的弓形的面积就是扇形的面积减去两个小三角形的面积,公式里面的很多东西都可以勾掉。对了,由于asin(a /
r)得到的是弧度,所以要乘一个180 ,再除一个PI 勾了以后,由于题目的r = 1
所以面积就相当的简洁。。。然后就和普通的二分一样了。这里就让 begin || end == mid
就可以了。所以最终一定会找到解得。所有的速度,都归结于那颗仰慕的树。。。。真是快。。。。
希望大牛指点。
再次感谢mengyou。
1 #include <stdio.h>
2 #include <math.h>
3 #define PI acos(-1.0)
4 #define B 1e-8
5 double cmp, area, a, b;
6 double getb(double ta){
7 double b = sqrt(1.0 - ta * ta);
8 double sja = ta * b;
9 double temp = asin(ta) - sja;
10 return temp / (area - temp);
11 }
12 int main(){
13 freopen("2346.in", "r", stdin);
14 freopen("2346.out", "w", stdout);
15 double begin, end, mid, bi, temp;
16 int i, j;
17 while(scanf("%lf%lf", &a, &b) != -1){
18 begin = 0.0;end = 2.0;area = PI;
19 if(a > b) bi = b / a;
20 else bi = a / b;
21 while(1){
22 mid = (begin + end) * 0.5;
23 temp = getb(mid * 0.5);
24 if(fabs(temp - bi) < B)break;
25 else if(temp < bi)begin = mid;
26 else end = mid;
27 }
28 printf("%.4lf\n", mid);
29 }
30 return 0;
31 }