Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Pascal. Определение числа закрашенных отрезков. (без рисования)

15K
29 января 2007 года
Салага
26 / / 19.12.2006
Дано:
Числовая прямая (от - 100 до +100)
Количество отрезков = N
Координаты отрезков: L - начало, К - конец.
Необходимо:
Определить число закрашенных отрезков. Учесть - если отрезок частично накладывается на отрезок - место наложения является дополнительным цветом.
Ввод-вывод осуществляется в файл/из онного.

Текст написан, но при увеличении числа наложений начинают счетчики слетать и приплюсовывать всякую ересь.

Код:
Program gg;
Var
        L:array [-100..100] of integer; {koordinata nachala otrezka}
        R:array [-100..100] of integer; {koordinati end'a otrezka}
        n, i, chist, dirty, Sdirty :integer;
    in_file, out_file :text;

BEGIN
chist:=0; { Zakrashennye 1 raz }
dirty:=0; { Zakrashennye 2 raza }
Sdirty:=0; { Zakrashennye n raz }


{Vvod massiva s koordinatami}
   Assign(in_file,'C:\cover.in');
   Reset(in_file);
    ReadLn(in_file,n);
        For i:=1 to n do
                 ReadLn(in_file, L,R);

   Close(in_file);

{End of the block}

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

{Block poiska chistih elementov}
       For i:=1 to n do
                 if (L<L[i+1])OR((R[i+1]<R)Or(R<L[i+1]))and(R>R[i-1]) then chist:=chist+1;
{end of the block}

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

{blok poiska grajznih elementov}

        For i:=1 to n do
                 If (L[i+1]<R)AND(L[i+1]>L) then dirty:=dirty+1;

{end of the block}

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

{ Blok poiska n zakrashennyh elementov }

        For i:=2 to n do
                if (L>L[i-1])AND(R>L[i+1])and(R[i+1]>R) then Sdirty:=sdirty+1;

{end of the block}

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
Assign(out_file,'C:\cover.out');
Rewrite(out_file);
        WriteLn (out_file,'dirty=',dirty);
        WriteLn (out_file,'chist=',chist);
        WriteLn (out_file,'Sdirty=',Sdirty);
Close(out_file);
ReadLn();
END.
268
29 января 2007 года
Михаил
587 / / 25.06.2005
1. Отрезки закрашены разными цветами?
2. Что значит дополнительный цвет?
15K
30 января 2007 года
Салага
26 / / 19.12.2006
1) Да, разными.
2) Если один отрезок накладывается на второй - эта часть тоже считается закрашенной т.е. смешанным, дополнительным цветом.

(L1)|-----|-------|--------|-------------|----------|---|(R1)~~|
(L2)|-------|--------|(R2)~~~~~~|~~~~~~|~~~~~~~|
(L3)|----------------------|(R3) L(4)|----------|R(4)

Вот рисунок - здесь представлено 4 отрезка, сделано "ступенькой", а вообще - они накладываются друг на друга.
На отрезке L1;R1 показаны точки начала и конца других отрезков.
Цвета всех отрезков неважны.
Всего закрашено - 7 частей числовой прямой.

~~~~~ - дополнительные "невидимые" линии, иначе - отображение косое получается.
268
30 января 2007 года
Михаил
587 / / 25.06.2005
1. что значит дополнительный цвет как он рассчитывается. Например смешали красный и белый какой получится, или это неважно?
2. интервал дополнительного цвета считать продолжением отрезка или это другой отрезок?
268
01 февраля 2007 года
Михаил
587 / / 25.06.2005
вобщем ведь можно просто идти от -100 до 100 и при изменении цвета текущей точки увеличивать счетчик на 1 и все
15K
01 февраля 2007 года
Салага
26 / / 19.12.2006
[QUOTE=Михаил;]1. что значит дополнительный цвет как он рассчитывается. Например смешали красный и белый какой получится, или это неважно?
[/QUOTE]
Неважно.

[QUOTE=Михаил;] интервал дополнительного цвета считать продолжением отрезка или это другой отрезок?
[/QUOTE]
Считать как новый цвет.


[QUOTE=Михаил;]вобщем ведь можно просто идти от -100 до 100 и при изменении цвета текущей точки увеличивать счетчик на 1 и все[/QUOTE]

А как быть с "пустотами"? Незакрашенными вообще отрезками? Цвет не указывается, просто имеется отрезок закрашенный как-нибудь.

А вот если самое минимальное значение начала принять за точку отсчета, а самое предшествующую максимальной по значению точки принять за значение остановки, а все и начальные и конечные точки забить в массив одномерный и отсортировать? И уже считать при наложении...
Работоспособно? Рационально?
268
02 февраля 2007 года
Михаил
587 / / 25.06.2005
ну с пустотами можно поступить так: проверять принадлежит ли точка интервалу отрезков. Если принадлежит то перед нами либо отрезок, либо их наложение, если проверять количество раз, которое точка принадледит, тогда можно однозначно сказать одному или нескольким, а если не принадлежит, то перед нами пустое пространство. Можно также оптимизировать, то есть проверять только на конечных точках интервала отрезка, а внутри его не проверять.
252
02 февраля 2007 года
koderAlex
1.4K / / 07.09.2005
если кодировать цвета как :
00h-бесцветный ,
01h-первый цвет
02h-второй
04h-третий
08h-четвёртый
10h-пятый
и т.д. ,то смешанные цвета окажутся закодированными одинаково.
проэцируем цвета в один массив операцией
X=(A)or(B)or(C)or(D)or(E)...
после этого считаем кол-во всех отрезков и кол-во бесцветных отрезков . их разность и будет кол-вом цветных отрезков .
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог