記事タイトルCoderforces 908 C New Year and Curling(暴力)

トランスファゲートhttp://codeforces.com/problemset/problem/908/C 标题:2次元座標系にはn個の半径rの円があり、最初は無限遠に出たxi位置で、それから順番に1個の円がy=0の方向に移動し、他の円にぶつかったりy=0にぶつかったりして停止し、最後に各円が最後に停止したときのy座標の位置を求めます.円が停止すると、他の円にぶつかっても移動しません.分析:まずデータは1000しかないので、直接暴力O(n 2)で解き、i番目の円について、1~i-1番目の円を巡り、i番目の円とぶつかるかどうかを判断し、ぶつかると、株の定理でy座標を求め、その後、遍歴して最大のy座標を求めたのが前円の座標位置コードである.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef pair<int ,int> pii;
typedef long long ll;

const int maxn = 1e5 + 10;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;

int n,r;
int x[maxn];
double y[maxn];//y   

int main()
{
    while (cin>>n>>r){
        for (int i=1;i<=n;i++){
            cin>>x[i];
        } 
        y[1]=r;
        for (int i=2;i<=n;i++){
            y[i]=1.0*r;
            for (int j=1;jif (fabs(x[j]-x[i])>2*r)continue;//       
                else {
                    int g = (2*r)*(2*r)-fabs(x[j]-x[i])*fabs(x[j]-x[i]);
                    double tmp = sqrt(g);
                    tmp += y[j];
                    y[i]=max(tmp,y[i]);
                }

            }
        }
        for (int i=1;i<=n;i++){
            if (i==1)printf ("%.8f",y[i]);
            else printf (" %.8f",y[i]);
        }
        printf ("
");
    }
    return 0;
}