查看CodeForces/336B的源代码 ←CodeForces/336B

[[分类:整数处理]]
==摘要==
{{信息题|Vasily the Bear and Fly|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70748#problem/G|1|100|遗漏情况|1|time=2015-02-27 12:35:20}}
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70748 2015 Winter Day 4 div1] G题
*原题链接：http://codeforces.com/problemset/problem/336/B
==题意==
坐标轴上有2*n个R为半径两两相邻的圆，问任取圆心第(1,i)和(2,j)<small>（i,j表示序号而非坐标）</small>之间的最短路径的数学期望（路径要求都在圆内）。
==题解==
*理解了题意确实做起来不是太难，肯定不能暴力，要优化到O(n)。
*很容易知道:|i-j|相等距离也相等，对于一个|i-j|，其符合条件的圆心对个数是(m-|i-j|)*2<small>（i=j时，没有*2）</small>。
*然后算一下距离乘下个数就好了，实际也没必要用高精度。但是被样例数据坑了。
*样例数据是这样：
{{无边框大照片|Knowledge/Algorithm/CodeForces/336B_1.jpg}}
*我以为这样也是最优：
{{无边框大照片|Knowledge/Algorithm/CodeForces/336B_2.jpg}}
*其实这样也OK……
{{无边框大照片|Knowledge/Algorithm/CodeForces/336B_3.jpg}}
<small>扯个题外话：java里BigDecimal的divide要求第二个参数是精度，不要漏了- -</small>
==代码==
{{折叠|336B.java代码已折叠
|<pre>import java.io.BufferedInputStream;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
  Scanner cin = new Scanner(new BufferedInputStream(System.in));
  int m = cin.nextInt();
  BigDecimal R = cin.nextBigDecimal();
  BigDecimal ans = BigDecimal.ZERO, TWO = BigDecimal.valueOf(2), s2 = new BigDecimal(
    Math.sqrt(2));
  for (int i = 0; i != m; ++i) {
   BigDecimal v = BigDecimal.ONE;
   BigDecimal u = BigDecimal.valueOf(i);
   u = u.add(BigDecimal.ONE);
   BigDecimal dis = BigDecimal.ZERO;
   if (u == v)
    dis = R.multiply(TWO);// 2R//
   else if (i == 1)
    dis = R.multiply(BigDecimal.valueOf(i * 2)).add(s2.multiply(R));// 2iR+R//
   else
    dis = R.multiply(BigDecimal.valueOf(i * 2 - 2)).add(
      s2.multiply(R.multiply(TWO)));// 2iR+R//
   if (i != 0)
    ans = ans.add(dis.multiply(BigDecimal.valueOf((m - i) * 2)));
   else
    ans = ans.add(dis.multiply(BigDecimal.valueOf(m - i)));
  }
  ans = ans.divide(BigDecimal.valueOf(m), 1000, RoundingMode.HALF_DOWN);
  ans = ans.divide(BigDecimal.valueOf(m), 50, RoundingMode.HALF_DOWN);
  System.out.println(ans);
  return;
 }
}
</pre>
|code336B}}