Ура! Решил с длинной арифметикой. eps = 0.0000000000000000000000000000000000000000000000000000000000000000001
Задача геометрически простая, но реализация в целой арифметике неприятная (ответ всё равно будет вещественный, но алгоритм можно сделать абсолютно точным при сравнении точек). Лучше использовать длинную вещественную арифметику.