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)の2点間の距離は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 ); } } }