Решение

Тема: геометрия, графы
Сложность: высокая

Сначала проверяем, не находится ли конечное положение монеты слишком близко к одной из других монет. Если `(D_i-D_1)/2` больше или равно расстоянию между центром `i`-й монеты и конечным положением 1 первой монеты, то выводим "NO" и завершаем выполнение программы.

Далее рассмотрим все пары монет, если расстояние между ними не позволяет провести между ними первую монету, то рисуем отрезок, соединяющий центры этих монет. Если расстояние между монетой и стенкой коробки не позволяет провести первую монету между ней и стенкой, рисуем перпендикуляр из центра монеты на соответствующую стенку.

В результате получается набор отрезков, разделяющий квадратное дно коробки на несколько областей. Если начальное и конечное положение монеты находятся в одной области, то головоломка решается, иначе – нет.

Реализацию этого алгоритма можно найти в задаче 5 областной олимпиады школьников по информатике 2005 года.