TurretPlacement

日課消化。頭悪いコード。たぶん、点を２０も３０も用意されたらアウト。
丸め誤差が発生するので、点Ｍと点Ｎの距離を求めるのにdouble(つまりsqrt）は使えない。幸い各点は-10000〜10000の格子点座標上にしか発生しないから、距離はint形式でも二乗のまま扱うことが出来る。
やはり問題は計算量。距離から組み合わせ数を自動的に出す必要あり。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class TurretPlacement {
private:

	int dist(int x1, int y1, int x2, int y2){
		int dx = x1 - x2;
		int dy = y1 - y2;
		return (dx*dx+dy*dy);
	}

	long long comb(int x1, int y1, int x2, int y2){
		long long num = 0LL;
		int tmp;
		tmp = dist(x1, y1, x2, y2) * 4;
		for(int i=1; i*i<tmp; i++){
			for(int j=1; (i+j) * (i+j) <= tmp; j++){
				num++;
			}
		}
		return num;
	}

public:
	long long count(vector<int> x, vector<int> y) {
		long long result = 0LL;
		for(unsigned int i=0; i<x.size()-1; i++){
			for(unsigned int j=i+1; j<x.size(); j++){
				result += comb(x[i], y[i], x[j], y[j]);
			}
		}
		return result;
	}
};

で、ちょっと考えてみたら、1+2+...+nで計算出来ますね、これ。
sqrtも問題じゃありませんでした。
ということで、完成版。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class TurretPlacement {
private:

	int dist(int x1, int y1, int x2, int y2){
		int dx = x1 - x2;
		int dy = y1 - y2;
		int dist = (int)(sqrt((dx*dx+dy*dy))*2);
		return dist;
	}

	long long comb(int x1, int y1, int x2, int y2){
		long long num = 0LL;
		int tmp;
		tmp = dist(x1, y1, x2, y2);

		num = ((tmp-1)*(tmp)/2);
		return num;
	}

public:
	long long count(vector<int> x, vector<int> y) {
		long long result = 0LL;
		for(unsigned int i=0; i<x.size()-1; i++){
			for(unsigned int j=i+1; j<x.size(); j++){
				result += comb(x[i], y[i], x[j], y[j]);
			}
		}
		return result;
	}
};