Codeforces #185 Div1. A. The Closest Pair

CF185はUnrateな回。でも本番Aしか解けなかったし、それも2WAしたのでunratedでよかった…。
http://codeforces.com/contest/311/problem/A

問題

2次元座標上にあるN個の点において、以下の手順で最も距離の近い点のペアを求めるアルゴリズムがある。

N個の点の座標をP[i]に入力し、Xが昇順で、次にYが昇順となるようにソート
for i=1～N
  for j=i+1～N
    tot++
    if P[j].x - P[i].x >= d then break
    dをP[i]とP[j]の距離で更新

上記コードでtotがK以上となるような点配置を答えよ。

解法

totがKぴったりじゃなくtot以上でいいので、とにかくtotを最大化すればよい。
全部の点のx座標を一緒にすればbreakしないのでtot=N*(N-1)/2になる。

ll N,K,T;
void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin >> N >> K;
	T=N*(N-1)/2;
	if(T<=K) {
		_P("no solution\n");
		return;
	}
	FOR(i,N) _P("%d %d\n",i,i*10000);
	return;
}

まとめ

Codeforcesはこういう変わった問題多いな。