найти сумму длин всех окрашенных частей прямой.

[vikka]

Люди! оч прошу вас мне помочь! мне на зачет по инфе нужно решить задачу! помогите пожалуйста это сделать! вот задача: на прямой окрасили N отрезков,известны координаты L [ i ] левого конца отрезка и координаты R [ i ] парвого конца i-ого отрезка для I = 1...n.
найти сумму длин всех окрашенных частей прямой.

нужно написать программу в паскале. ( для решения нужно рассмотреть 2 случая, если отрезки пересекаются и если отрезки не пересекаются)

[evg_m]

1. берем новый отрезок L(i), P(i)
2. проверяем пресекался ли он с использоваными ранее
3. если да то выделяем из него ненепересекающуюся часть иначе используем весь. L1(i), P1(i)
4. считаем общую длину
5. если остались отрезки, то повторяем п.1.

[vikka]

так то я все это понимаю.....у меня не получается правильно написать саму программу!!

[evg_m]

пример неправильной программы чтобы было что исправлять

[vikka]

program n1;
uses crt;
var L,R:array[1..1000] of real;
i,N:integer;
Sum:real;
begin
clrscr;
Sum:=0;
writeln('input N:');
readln(N);
writeln('vvedite koordinati otrezkov');
for i:=1 to N do
begin
read(L[i],R[i]);
Sum:=Sum+abs(R[i]-L[i]);
readln;
end;
writeln('summa ravna ',Sum:7:4);
readln;
end.
здесь вроде как получается,что рассмотрен случай когда отрезки не пересекаются. что нужно поменять( добавить и тп) чтобы рассмотреть с пересечением отрезков

[evg_m]

для облегчения рисуем на прямой возможные варианты взаимного положения двух отрезков 1 и 2

L[1]<L[2] and R[1]<L[2] 1 слева от 2 без пересечения новая часть L[2]R[2]
L[1]<L[2] and R[1]>L[2] and R[1]<R[2] 1 слева от 2 с пересечением новая часть R[1]R[2]
L[1]<L[2] and R[1]>L[2] and R[1]>R[2] 1 полностью включает 2 новая часть R[1]R[1] т.е. отсутствует
продолжая таким образом составляем условия и правила для других случаев.

L1[i]:=L[i]; R1[i]:=R[i];
for j:=1 to i-1 do //сравниваем текущий отрезок
begin // со всеми предыдущими (точнее с их непересекающейся частью
if (R[i]<L[j]) then //нет пересечения лежит слева
begin L1[i]:=L[i]; R1[i]:=R[i]; end //выделяем новую непересекающуюся часть(в данном случае она не изменялась)
else if (L[i]<L[j]) and (R[i]>L[j]) and (R[i]<R[j]) then // 1 слева от 2 с
пересечением
begin L1[i]:=R[j]; R1[i]:=R[i]; end //отрезали кусок пересечения слева
else if ...
//перечисляем все случаи сформированные ранее

end;
// здесь L1[i], R1[i] непересекающаяся часть исходного отрезка L[i],R[i]

надеюсь принцип понятен

[evg_m]

подумал немножко и нашел "неудобный случай" для данного алгоритма,
а именно когда большой новый отрезок полностью включает маленький предыдущий. По алгоритму он должен был бы разбиваться на два отрезка (до и после маленького). Но в алгоритме изменения числа отрезков не предусмотрено, хотя это можно сделать.

[vikka]

вот и преподаватель мне сразу этот случай показал, когда один или несколько отрезков лежат в одном большом. это можно сделать?

[como]

Сообщение от vikka

вот и преподаватель мне сразу этот случай показал, когда один или несколько отрезков лежат в одном большом. это можно сделать?

Можно. Эти отрезки нужно просто отбросить.

[vikka]

оооо,все просто ужасно!=((( напишите ПОЖАЛУЙСТА полностью код программы, я окончательно запуталась!!пожалуйста....