Олимпиадные задачи по программированию. Ч. 2. Лучшие решения. Ускова О.Ф - 17 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

dec(mkr[krol[2]])
end
else dec(mkr[krol[2]])
end
end
end;
close(fkr)
end;
procedure output(s1:word);{Вывод кроликов}
var marr:string[5];
begin
assign(fkr,'output.txt');
rewrite(fkr);str(s1,marr);write(marr);
writeln(fkr,marr);
close(fkr)
end;
begin
input;
married(s1);
output(s1)
end.
Задача 5. "Divide et impkra!"
Задача предлагалась на областной олимпиаде школьников в 1998 году
и на факультетской олимпиаде в 1999 году. Автор решения – один из
победителей олимпиады, ныне магистрант второго года обучения Вахтин
Алексей Александрович.
На плоскости задано N прямых. Напишите программу для определения, на сколько частей
разбивают плоскость эти прямые.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени : 20 секунд .
Формат входных данных:
Исходные данные во входном файле записаны в следующем порядке: N, a
1
, b
1
, c
1
, d
1
,… , a
N
, b
N
,
c
N
, d
N
, где 1<=N<=100, а пары чисел (a
i
,b
i
) и (c
i
,d
i
) – целочисленные координаты двух различных
точек, через которые проходит прямая с номером i. Все данные разделяются пробелами и/или
символами перевода строки .
Формат выходных данных:
В выходной файл необходимо вывести одно целое число – искомое количество кусков.
Пример входных и выходных данных
INPUT.TXT OUTPUT.TXT
3 7
0 0 0 2
0 2 2 0 2 0 0 0
Алгоритм :
Количество частей, на которые делят линии плоскость, зависит от числа несовпадающих
линии и числа пересечений каждой линии.
Сначала отбросим все совпадающие линии и найдем все точки пересечений. Пусть
несовпадающих линий k. Тогда минимальное число частей k+1 (линии параллельны ). Возьмем
первую точку пересечений. Пусть в ней пересекается n
1
линий. Тогда к количеству частей (k+1)
прибавляется n
1
-1 частей. Возьмем вторую точку пересечений. Пусть в ней пересекается n
2
линий. Тогда к количеству частей прибавляется еще n
2
-1, и так далее, пробегая все точки
пересечений, получим количество частей, на которые делят линии плоскость.

Страницы