Здравствуйте, www, Вы писали:

www>вам иннтересно как найти с какой стороны лежит точка (i.e. в какую сторону двигаться байнари серчем?)
www>если да, то мне кажется *самый простой* способ будет векрторное произведение.
www>строите векторное произведение 2 векторов: от начальной точки до искомой и от начальной до текущей (которую получили бинарным поиском). Далее вектор (0, 0, x1*y2-y1*x2) есть их векторное произведение (детерминант трехмерной матрицы|(e1,e2,e3)(x1,y1,0)(x2,y2,0)|. Далее правило правой руки, если он направлен вверх, то вам нужно двигаться в одну сторону, вниз — в другую.

www>Школьная математика тоже подойдет, если вы не помните векторное произведение.

Да, это оптимальное решение.
Проблемма не в векторном произведении и не в школьной математике. Я уверен что решил бы эту задачу имея достаточно времени, но за 15 минут — однозначно нет. Может быть для тех, кто занимается, скажем, программированием игр, или другими вещами связанными с геометрией это очевидно, но у меня голова была забита другим на тот момент. И насколько я знаю именно на этой задачке все засыпались в тот день, когда я проходил собеседовние.
Вот мне просто интересно, понять кание критерии отбора были у Майкрософта, если люди решили сложную задачу и их взяли, не решили — не взяли — это понятно. Если же не решили и их взяли — значит были какие-то другие аргументы "за".