Codeforces #185 Div2 C "The Closest Pair"

問題

http://codeforces.com/contest/312/problem/C

訳

今、Tinyは計算機科学について学んでいる。"The Closest Pair Of Points In The Plane"という課題をとく事に挑戦したとき、彼はTLEとなる入力が存在する事に気付いた。

この課題は以下のようなものだ。nポイント座標上に与えられるので、距離が最小のポイントのペアを見つけよ。(x1, y1)と(x2, y2)の２点間の距離はsqrt( (x1 - x2)^2 + (y1 - y2)^2 )である。

TLEとなる擬似コードは以下のようなものである。

input n
for i from 1 to n
    input the i-th point's coordinates into p[i]
sort array p[] by increasing of x coordinate first and increasing of y coordinate second
d=INF        //here INF is a number big enough
tot=0
for i from 1 to n
    for j from (i+1) to n
        ++tot
        if (p[j].x-p[i].x>=d) then break    //notice that "break" is only to be
                                            //out of the loop "for j"
        d=min(d,distance(p[i],p[j]))
output d

ここで、totはこのコードの実働時間と見てよい。動かすコンピューターでは、このtotがkを超えてしまうとTLEとなってしまう。

彼のコードをTLEとさせるような入力を作成せよ。

考えた事

yについて何にも対策とって無いから、xは0で固定にして縦に一列に点を並べてしまえばよい。

ソースコード

int main() {
    int n, k;
    cin >> n >> k;

    int maxTime = n * (n - 1) / 2;
    if( maxTime <= k ){
        cout << "no solution" << endl;
    }else{
        int x = 0;
        for( int y = 0; y < n; y++ ){
            printf( "%d %d\n", x, y );
        }
    }
}