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.
Pascal. Определение числа закрашенных отрезков. (без рисования)
Числовая прямая (от - 100 до +100)
Количество отрезков = N
Координаты отрезков: L - начало, К - конец.
Необходимо:
Определить число закрашенных отрезков. Учесть - если отрезок частично накладывается на отрезок - место наложения является дополнительным цветом.
Ввод-вывод осуществляется в файл/из онного.
Текст написан, но при увеличении числа наложений начинают счетчики слетать и приплюсовывать всякую ересь.
Код:
2. Что значит дополнительный цвет?
2) Если один отрезок накладывается на второй - эта часть тоже считается закрашенной т.е. смешанным, дополнительным цветом.
(L1)|-----|-------|--------|-------------|----------|---|(R1)~~|
(L2)|-------|--------|(R2)~~~~~~|~~~~~~|~~~~~~~|
(L3)|----------------------|(R3) L(4)|----------|R(4)
Вот рисунок - здесь представлено 4 отрезка, сделано "ступенькой", а вообще - они накладываются друг на друга.
На отрезке L1;R1 показаны точки начала и конца других отрезков.
Цвета всех отрезков неважны.
Всего закрашено - 7 частей числовой прямой.
~~~~~ - дополнительные "невидимые" линии, иначе - отображение косое получается.
2. интервал дополнительного цвета считать продолжением отрезка или это другой отрезок?
вобщем ведь можно просто идти от -100 до 100 и при изменении цвета текущей точки увеличивать счетчик на 1 и все
[/QUOTE]
Неважно.
[QUOTE=Михаил;] интервал дополнительного цвета считать продолжением отрезка или это другой отрезок?
[/QUOTE]
Считать как новый цвет.
[QUOTE=Михаил;]вобщем ведь можно просто идти от -100 до 100 и при изменении цвета текущей точки увеличивать счетчик на 1 и все[/QUOTE]
А как быть с "пустотами"? Незакрашенными вообще отрезками? Цвет не указывается, просто имеется отрезок закрашенный как-нибудь.
А вот если самое минимальное значение начала принять за точку отсчета, а самое предшествующую максимальной по значению точки принять за значение остановки, а все и начальные и конечные точки забить в массив одномерный и отсортировать? И уже считать при наложении...
Работоспособно? Рационально?
ну с пустотами можно поступить так: проверять принадлежит ли точка интервалу отрезков. Если принадлежит то перед нами либо отрезок, либо их наложение, если проверять количество раз, которое точка принадледит, тогда можно однозначно сказать одному или нескольким, а если не принадлежит, то перед нами пустое пространство. Можно также оптимизировать, то есть проверять только на конечных точках интервала отрезка, а внутри его не проверять.
00h-бесцветный ,
01h-первый цвет
02h-второй
04h-третий
08h-четвёртый
10h-пятый
и т.д. ,то смешанные цвета окажутся закодированными одинаково.
проэцируем цвета в один массив операцией
X=(A)or(B)or(C)or(D)or(E)...
после этого считаем кол-во всех отрезков и кол-во бесцветных отрезков . их разность и будет кол-вом цветных отрезков .