SRM 465 250pt: TurretPlacement

TopCoder

問題概要

点がN(<50)個与えられる(abs(x), abs(y) < 10000)。この中から2つ選んで、そこを中心として辺の長さが整数な正方形を2つ設置する。正方形が交わらないような組み合わせが何通りあるか求める問題。

考えたこと

  • (本番はsqrtを使って浮動小数点使ったためEPS入れてないとかどうのこうので余計な不安を感じてしまった。一応通ってはいたけど)
  • 基本はいつでも全探索。2点を固定して、もう一方の長さも固定すると後は簡単に計算できる。
  • なるべく浮動小数点数は扱わない。全部整数で計算する様に書く。
    • とはいえ浮動小数点数を扱わないことが目的化しないようにせねば。
  • 和の計算で微妙に間違えて時間かかったけど無事通った。

practiceで通ったコード

計算量O(N^2 * MAX_X)。簡単な計算とsqrtを使えばO(N^2)までは簡単に落とせる。

#include <vector>
using namespace std;

typedef long long int64;

struct TurretPlacement {

	int64 count(vector <int> xs, vector <int> ys) {
		const int N = xs.size();

		int64 ret = 0;
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				int64 r = (sq(xs[i]-xs[j]) + sq(ys[i]-ys[j]));
				int64 sum;
				for(sum=1; sum*sum <= 4*r; sum++);
				sum--;
				sum -= 1;
				ret += sum * (sum + 1) / 2;
			}
		}

		return ret;
	}

	int64 sq(int64 x){
		return x*x;
	}
};