Задачи районных олимпиад по программированию

3. Если A[S]=1 или A[S]=4, то полагаем ^ [ Т ] ^ ^ . Все элементы массива, номера которых были текущими на каком-либо шаге, получают те же значения, что и A[S]. 4. Если A[S]=0, то S становится текущим числом. Выполняем переход на пункт 2. Массив А после заполнения будем использовать для дальнейшей работы. Для всякого числа i из промежутка от 1 до N находим сумму квадратов его цифр S и выводим A [i], если окажется, что A [S]=1. 97.ПР1. Решение задачи распадается на ряд этапов: • Получение уравнений прямых, содержащих заданные отрезки. Уравнение прямой, проходящей через точки (xi, yi) и (xi+1, имеет вид: x -xi = У -yi xi + l - xi yi+ l - yi ' Во избежание ошибки типа "деление на ноль" уравнение лучше записать в таком виде: У (x+i - xi) + x (у{ -y1+l) = yi xm - Xiy1+l. • Нахождение точек пересечения прямых, содержащих отрезки. Пусть один из отрезков определяется точками A(xi, y1) и В(х1+1, yi+1), а второй - точками C(xj, yj) и D(x]+1, yJ+1). Им соответствуют уравнения прямых: для первого отрезка - y (xi+1 - xi) + x (yi - yi+1) = yi xi+1 - xi yi+1 , для второго отрезка - y (xJ+1 - xj) + x (y}- - yj+1) = y}- xj+1 - x}-yj+1. Полагая x%+1 - x% = аъ yi - ym= bu yi xi+1 - xi yi+1 = еъ xj+1 - xj = ^ yj - yj+1= b2, yj xj+1 - xjyj+1 = c2, найдем x иy по формулам: y = Л1/Л , x = А2/А , где Л = а1 b2- а2 bu Л1 = С1 b2- С2bb Л2 = а1 С2- а2 С1 (Л Ф 0). 29