Создание невырожденного набора точек в 2D - C ++

Я хочу создать большой набор случайных облаков точек в 2D-плоскости, которые не являются вырожденными (во всем наборе нет 3 точек на прямой линии). У меня есть наивное решение, которое генерирует случайную пару с плавающей запятой P_new (x, y) и проверяет каждую пару точек (P1, P2), сгенерированную до сих пор, если точка (P1, P2, P) находится в одной строке или нет. Это требует O (n ^ 2) проверок для каждой новой точки, добавленной в список, что делает всю сложность O (n ^ 3), что очень медленно, если я хочу сгенерировать более 4000 точек (занимает более 40 минут). Есть ли более быстрый способ сгенерировать этот набор невырожденных точек?