Как определить отрезок, пересекающий наибольшее количество прямоугольников

[Daniel0K]

Суть такова, есть n прямоугольников со сторонами, параллельными осям координат, заданных координатами своей левой верхней и правой нижней вершин, и m отрезков, заданных координатами своих концов. Нужно определить отрезок, пересекающий наибольшее количество прямоугольников
Не могу придумать единое условие для определения таких отрезков. Есть идеи?

[s-andriano]

Что такое "определение отрезков"?
Тип данных для представления отрезка?
В таком случае отрезок определяется через две точки, т.е. вводим структуру - вектор, а потом - отрезок, состоящий из двух векторов.

[Daniel0K]

Опеределение? т.е. мне нужно найти координаты конца и начала такого отрезка.
координаты вещественные.
Я с помощью записей сделал массивы координат прямоугольников и отрезков, а вот как дальше применить ...

[s-andriano]

Не понял.
Зачем искать то, что задано по условию задачи?

[ViktorR]

Например, простой перебор.
1. Пишем функцию, которая определяет пересекаются ли два отрезка.
а) Решение системы двух линейных уравнение
б) Проверка, что точка пересечения, если таковая найдена,
принадлежит одному из отрезков.

2. В цикле 1:
Берём отрезок
В цикле 2:
Для каждого прямоугольника готовим 4-е уравнения.
Если есть пересечение, то +1 и выходим из цикла.
// Для прямоугольника достаточно обнаружить одно пересечение
Конец цикла 2;
Конец цикла 1;

3. Полученный массив, в котором есть координаты отрезков и число пересечений просматриваем на поиск максимума пересечений.


Ну, как-то так ...