C. Хамгийн ойр хос

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Тини тооцооллын геометр сурч байгаа. Тэрээр "Хавтгай дээрх хамгийн ойр хос" гэж нэрлэгдсэн бодлогыг бодох гэж оролдож байхдаа дараах буруу асимптотик үнэлгээтэй код хугацааны хязгаарлалт хэтрэлгүй тэнцсэн байхыг олов.

Бодлого нь хавтгайд $n$ цэг өгөгдөв. Хоорондох зай нь хамгийн бага байх хос цэгийг олох байв. $(x_1, y_1)$ болон $(x_2, y_2)$ цэгийн хоорондох зайг томьёогоор олно.

Уг кодны псеодо код нь дараах хэлбэртэй байв.

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$-аас их болвол хугацааны хязгаарлалт хэтэрнэ.

Та үнэхээр сайн хакер учир Тинид дээрх кодонд хугацааны хязгаарлалт өгөх тест бэлдэхэд нь туслана уу.

Оролт

Нэг мөрөнд $n$, $k$ ($2 ≤ n ≤ 2000$, $1 ≤ k ≤ 10^9$) тоо өгөгдөнө.

Гаралт

Уг кодонд хугацааны хязгаарлалт өгөх тест байхгүй бол "no solution" гэж хашилтгүйгээр хэвлэнэ. Хэрвээ тийм тест олдвол $n$ мөрөнд цэгийн координат $x_i, y_i$ ($|x_i|, |y_i| ≤ 10^9$)-г дунд нь хоосон зайгаар тусгаарлаж хэвлэнэ. Цэгүүд дараах нөхцлүүдийг хангаж байх ёстой.

  • Бүх цэг ялгаатай байна
  • $|x_i|, |y_i| ≤ 10^9$
  • Код ажиллаж дууссаны дараа $tot$ нь $k$-аас их болсон байх ёстой.

Орчуулсан: Говьхүү

Жишээ тэстүүд

Оролт
4 3
Гаралт
0 0
0 1
1 0
1 1
Оролт
2 100
Гаралт
no solution
Сэтгэгдлүүдийг ачааллаж байна...