SRM465 Div1 Easy(250), Div2 Medium(500) 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; }