Решение задачи Пара прямых с Codeforces
С пояснением   Просмотров: 62
Необходимо узнать, существуют ли две такие прямые, что каждая из заданных точек принадлежит хотя бы одной из них. Прямые могут совпадать.
Пояснение к задаче
Если точек меньше 3, то ответ YES. Иначе зафиксируем первые 3 точки. Проверим, правда ли 1-я и 2-я точки могут лежать на одной прямой. Для этого удалим все точки, которые попали на прямую, проходящую через точки 1 и 2, и проверим, правда ли оставшиеся точки лежат на одной прямой. Если нет, то аналогично проверим, правда ли, что точки 1 и 3 могут лежать на одной прямой. Если снова нет, то прямая, проходящая через точку 1, не может содержать точки 2 и 3, а, следовательно, 2 и 3 должны лежать на одной прямой. Если и сейчас не получилось разместить точки, то ответ NO.
Проверка, лежат ли точки a, b и c на одной прямой может быть сделана подсчетом псевдо-векторного произведения (b - a) × (c - a). Оно равно 0 когда вектора (b - a) и (c - a) коллинеарны.