Jokerjar79
Advanced Member | Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Я решал нечто подобное. Если не брать во внимание радиусы (то есть работать с точками). Разбиваем все точки на пары точек. Например, три точки: 1, 2, 3 разбиваются на 1 - 2, 1 - 3, 2 - 3. Пара точек - это некоторая прямая, проходящая через них, характеризующаяся в системе координат двумя параметрами - a и b (y = ax + b). Находим для всех пар эти a и b, занося их в отведенный массив (массив структур, т.е. a и b - это один элемент массива). Далее сортируем этот массив. В итоге, пробежав по массиву мы можем найти самую длинную последовательность пар точек, лежащих на одной прямой (то есть последовательность элементов с одинаковыми а и одинаковыми b в отсортированном массиве). Зная это число (число пар) можно определить и число точек, лежащих на одной прямой. Для не точек а шаров все аналогично, разве что при нахождении последовательности a и b сверяются не жестко а с учетом радиуса.
Параметр a для пары точек p1 и p2 считается так: a = (p1.y - p2.y) / (p1.x - p2.x);
b = p2.y - a*p1.x; |
