Версия для печати темы

Автор: maksimla 2.11.2008 16:09

есть разукрашены n прямых отрезки. Даны этих каждого отрезка правого и левого координаты концов Li и Ri здесь i = 1,..,n. Напишите программу, находящую раскрашенных прямых половины длины.
Первичные данные записаны в файле duom.txt. На первой строчке написан натуральное число n
(1<=n<=1000). Патом на следущих n строчек записаны два натуральных числа , отделены одним пробелом, значющие правого и левого координаты концов L и R (-100000<=l<r<=100000). Результаты - раскрашенных прямых записать в файл rez.txt.
пример
начальные данные
5
-1 1
7 8
3 5
-2 2
4 6
результат
8

объяснение
отрезок (-1 1) находится в отрезке (-2 2) в середине, поэтому их общяя длина равна отрезку (-2 2) длины 4.
отрезок (3 5) и (4 6) соединяются и тоэтому общий отрезок (3 6) и длины 3. Непересикающиеся отрезки (-2 2),(3 6), (7 8) их общяя сума длины равна 4 + 3 + 1 = 8.

Автор: Lapp 2.11.2008 18:51

Я не вполне понял, при чем тут половина
Короче, вот тут реализован алгоритм нахождения суммарной длины после наложения:

  for i:=1 to n do for j:=1 to n do
    if (i<>j)and(R[i]>=L[j])and(L[i]<=R[j]) then begin
      if L[i]>L[j] then L[i]:=L[j];
      if R[i]<R[j] then R[i]:=R[j];
      L[j]:=R[j];
    end;
  s:=0;
  for i:=1 to n do s:=s+R[i]-L[i];

Если будут вопросы - задавай.

Автор: maksimla 2.11.2008 21:26

if (i<>j)
почему так ведь i=j всегда

Автор: Lapp 3.11.2008 2:38

Нет, не всегда. Для каждого значения i перебираются все значения j.
А нужно это для того, чтоб не сравнивать отрезок с самим собой.