Вопрос к программистам

Естественно, в тестах будут и пересечения, и совпадающие участки пути. На то она и олимпиада.
А вот использование массивов минимум некрасиво, максимум не пройдёт по ограничениям памяти или времени.

Предлагаю решение без массивов, с небольшим количеством итераций и довольно красивое

цикл по отрезкам (1000 итераций)

   Для каждого отрезка A(x1,y1,z1), B(x2,y2,z2) рассчитаем  dx=x2-x1, dy=y2-y1, dz=z2-z1.    k=НОД(dx,xy,dz).

   k-1 - количество целочисленных узлов внутри  интервала AB.

   увеличиваем счётчик на k-1
цикл перебор всех ранее пройденных отрезков и проверка пересечения с текущим (грубая оценка - 1000 итераций)

       если пересечений нет - нет действий

       если пересечение в единственной точке - уменьшаем счётчик на 1

       если пересечение на интервале - выясняем сколько целочисленных внутренних узлов текущего отрезка попало в пересечение (kp) и уменьшаем счётчик на kp

увеличиваем счётчик на N - заданные узловые вершины.


Максимальное количество итераций 499500 < 10^6.

Прим.: при dx=0 рассчитываем НОД(dy,dz). C другими координатами - аналогично.

Вчера / сегодня проходил муниципальный этап Всероссийской олимпиады школьников...
Что интересно - задания наконец-то сделаны с толком)) Правда мы всё равно на этапе проверки нашли косяки - в тестах... Но тем не менее - прогресс, задания по силам школьникам...