SRM465 Div1 Easy(250), Div2 Medium(500) TurretPlacement

TurretPlacement

ある地点AとBに塔を作るとき、塔の大きさを最も大きくできるのは塔がAとBを結ぶ線分に平行な場合で、塔の大きさの和は最大でAとBの距離の倍。和がdになるような大きさの選び方はd(d-1)/2通り。

#include <vector>
#include <cmath>

using namespace std;

class TurretPlacement
{
public:
    long long count( vector <int> x, vector <int> y );
};

long long TurretPlacement::count( vector <int> x, vector <int> y )
{
    int n = (int)x.size();

    long long r = 0;

    for ( int i=0; i<n; i++ )
    for ( int j=i+1; j<n; j++ )
    {
        long long d = (long long)( sqrt( pow((double)x[i]-x[j],2) + pow((double)y[i]-y[j],2) ) * 2 );

        r += d*(d-1)/2;
    }

    return r;
}