Dima TДиагонали тоже можно учесть, но ты этим "крестом" покрыл 5/9 всего пространства, если поле увеличить, то твой крест все большую часть занимать будет. Т.е. КПД будет все хуже по сравнению с тупым перебором.
ИМХУ тут лучше перебора нет вариантов. Разве что при поле 100500*100500 перегнать все в таблицу и дальше SQL. Хотя тут тоже не уверен что возможны идеальные решения.
Дима. "Крест" дает быстрый ответ в случае негативного расклада исходных данных.
Но для утвердительного все равно нужно найти хотя-бы 1 первый попавшийся отрезок.

По поводу оптимизации. Если мы посмотрим на задачу под углом мат-статистики то поиск
отрезка нужно начинать не слева направо а от центра в разные стороны.