MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks

感谢   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 }

 

posted on 2008-09-04 00:32 memorygarden 阅读(325) 评论(0)  编辑 收藏 引用 所属分类: 报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理