首页 > ACM题库 > HDU-杭电 > HDU 4808-Drunk[解题报告]HOJ
2015
09-18

HDU 4808-Drunk[解题报告]HOJ

Drunk

问题描述 :

Jenny is seriously drunk. He feels as if he is in an N-dimension Euclidean space, wandering aimlessly. In each step, he walks toward some direction and the “length” of each step will not exceed R. Technically speaking, Jenny is initially located at the origin of the N-dimension Euclidean space. Each step can be represented by a random N-dimension vector(x1, x2, … , xn) chosen uniformly from possible positions satisfying xi >= 0 and x12 + x22 + … <= R2.
Assume the expectation of his coordinate after his first step is (y1, y2, … , yn). He wants to know the minimum yi .

输入:

There are several (about 100,000) test cases, please process till EOF.
Each test case, only one line contains two integers N and R, representing the dimension of the space and the length limit of each step.(1 <= n <= 2 * 105, R <= 105).

输出:

There are several (about 100,000) test cases, please process till EOF.
Each test case, only one line contains two integers N and R, representing the dimension of the space and the length limit of each step.(1 <= n <= 2 * 105, R <= 105).

样例输入:

2 1

样例输出:

0.4244131816

题意:给定一个n维欧几里德空间中的一个n维向量(x1,x2,..,xn),xi>=0,sigma(xi^2)<=R^2.问xi最小值的期望.
解法:注意到空间球体的强对称性,即求x方向上的期望.这可以通过积分得出.在积分的过程中注意可以假设n维球体的体积为Vn=Pn*R^n.
#include <cstdio>
#include <cmath>
const int MAXN = 200000 + 5;

double t[MAXN];

int main()
{
    t[0] = acos(-1) / 2., t[1] = 1.;
    for (int i = 2; i < MAXN; ++ i) {
        t[i] = t[i - 2] * (i - 1) / i;
    }
    int n, R;
    while (scanf("%d%d", &n, &R) == 2) {
        double res = .5 * t[n + 1] * R / t[2];
        printf("%.10lf\n", res);
    }
    return 0;
}

参考:http://blog.csdn.net/u011277193/article/details/40735371


  1. 任何国家,都不可能在无利可图的情况下干涉其他国家,不然对得起本国的纳税人吗?不捐钱买战斧就想老美出手?玩蛋去吧!

  2. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  3. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  4. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  5. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  6. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  7. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  8. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  9. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  10. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  11. 诚聘:网络操作人员.有电脑手机的都能在家上班赚钱.时间自由.工资曰结50-300不等.详询***2528309742.咨询一下不会吃亏.此广告长期有效!

  12. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  13. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  14. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  15. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  16. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  17. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  18. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  19. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  20. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  21. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  22. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  23. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  24. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  25. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  26. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  27. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。

  28. 泉老师,您是“雀战”老手。俺从来没有和您在麻将桌上交流过,只是在您的博客上交流些思想,却出现了“对点子”,请您不要误会。