Давайте решать GRE задачи вместе?

[future]

Три пересекаются треугольником. Четвертая не параллельна ни одной из них и не проходит через уже имеющиеся точки пересечения.

[Десятник-аспирант]

Больше 6 пересечений действительно придумать не смог.
Три линии пересекаются "треугольником" для максимального кол-ва точек.
Четвёртая (вертикальная) должна пересекать все предыдущие три для той же цели (макс. кол-во точек).
Классический пример greedy strategy на каждой итерации (здесь добавления каждой новой линии) - каждый цикл должен приносить нам наибольший результат.

[future]

Больше 6 пересечений действительно придумать не смог.

Ну, это ведь и невозможно. Любые две линии могут иметь не больше одной точки пересечения (для наших целей совпадающие линии не рассматриваются, вестимо). То есть первые две линии имеют максимально одну точку пересечения, если они не параллельны. Третья может максимально добавить нам две точки пересечения - по одной с каждой имеющейся линией, если она не параллельна двум предыдущим и не проходит через точку их пересечения. Больше технически невозможно, исходя из первого утверждения. Четвертая, по той же причине, может добавить максимум три точки пересечения (если она не параллельна трем предыдущим и не проходит через точки их пересечения). Итого 1+2+3=6.
По сути то же, что написал ты, конечно, но с другого ракурса
А про greedy strategy не слышала, интересно

[victor_a]

с другого ракурса

Самый удобный и универсальный ракурс в случае таких задач -- следующий:

f(n) -- максимальное количество пересечений n линий на плоскости. Например, f(0) = f(1) = 0, так как пересечений нет вообще. Представьте что у вас есть n линий с максимальным f(n) кол-вом пересечений. Добавив еще одну линию (которую всегда можно провести непараллельно любому конечному количеству линий) вы получите максимум n новых пересечений (одно пересечение с каждой из ранее присутствовавших линий). То есть, f(n+1) = f(n) + n (или f(n) = f(n-1) + (n - 1), что то же самое). Имея на руках начальное условие f(1) = 0 и (рекуррентное) соотношение f(n) = f(n-1) + n - 1, вы можете последовательно посчитать f для любого положительного аргумента. Например, f(4) = f(4 -1) + 4 - 1 = f(3) + 3 = (f(3 - 1) + 3 - 1) + 3 = (f(2 - 1) + 2 - 1) + 2 + 3 = f(1) + 1 + 2 + 3 = 1 + 2 + 3 = 6. Если числа маленькие, то можно просто нарисовать картинку и прикинуть f(n). Если спрашивают про f(10), то картинка уже мало поможет, и придется решать по-честному.

Если требуется посчитать f(n) с очень большим аргументом (n > 20), то на последовательный подсчет может не быть времени. В таком случае, вы можете получить явное выражение для f(n) (как функции n): f(n) = f(n - 1) + (n - 1) = f(n - 2) + (n - 2) + (n - 1) = f(n - 3) + (n - 3) + (n - 2) + (n - 1) = (...угадываем...) = (n - (n - 1)) + (n - (n - 2)) + ... (n - 3) + (n - 2) + (n - 1) = 1 + 2 + 3 + ... + (n - 2) + (n - 1) = (-- сумма арифметической прогрессии) = (1 + (n - 1)) * (n - 1) / 2 = n * (n - 1) / 2. Таким образом, f(100) = 100 * 99 / 2 = 50 * 99 = 50 * (100 - 1) = 5000 - 50 = 4950.

[future]

Ага, максимально полный ответ. Обобщения вообще помогают жить. И сдавать экзамены

[Maxim]

На самом деле даже сумму арифметической прогрессии знать не надо. У нас есть n линий. Каждая пересекается с каждой по одному разу. Посчитаем количество точек пересечения. Каждая из n линий перескается с каждой из оставшихся n-1 линий. Т.е. имеем n*(n-1). Но таким образом мы посчитали каждую точку пересечения два раза (один раз когда линия A пересекалась с линией Б и другой раз наоборот), т.е. окончательный ответ: n*(n-1)/2