CF336B[思维题]-白红宇

CF336B[思维题]

阅读量：4970 次

发布时间：2019-06-12

本文共 936 字，大约阅读时间需要 3 分钟。

题目链接【http://codeforces.com/problemset/problem/336/B】

题意：画出2*m个圆圈，编号为1-m的圆圈在同一行相邻，编号在m+1-2*m的圆圈在同一行，有m*m次操作，每次操作要小从v的圆心到达u的圆心，并且只能走圆的的内或圆环上，求这m*m次操作的平均。

v=i/m+1，u=m+1+(i%m)，（第i次操作）。

题解：由v,u的表达式可以知道这m*m次操作分别是1-m的每个点与[m+1,2*m]之间的距离。两个圆心之间的最短距离共有三种情况，在同一列，最短距离就是圆心的连线，水平位置相邻，距离为（2+sqrt(n)）*R,水平位置不相邻，那么距离为（2+2*sqrt(n))*R+(相对距离-1)*2*R，注意这是个等差数列，可以在线性时间内求出来;

#include#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int m, R;double ans=0.0;double t=sqrt(2.0);void get_ans(int x,int y){    int k=0;    if(x) ans+=2+t,x--;    if(y<=m) ans+=2+t,y++;    if(x) k=x,ans+=(k+2*t+1)*k;    if(y<=m) k=m-y+1,ans+=(k+2*t+1)*k;}int main (){    scanf("%d%d", &m, &R);    for(int i=1;i<=m;i++)    {        ans+=2.0;        get_ans(i-1,i+1);    }    ans=ans/m*R/m;    printf("%.10f\n", ans);    return 0;}

转载于:https://www.cnblogs.com/pealicx/p/6561602.html

你可能感兴趣的文章