Форум на Исходниках.RU

Сортировка

Visitor — Tue, 09 Dec 2003 13:24:54 +0000

Visitor: Паскаля под рукой нет. На Си -- вот:
overlay.cpp

#include <stdlib.h>
#include <stdio.h>

typedef struct __tagpoint{
double x;
int isbegin;
} pnt, *ppnt;

int compareOpen(const void *ppnt1, const void *ppnt2)
{
if(((ppnt)(ppnt1))->x > ((ppnt)(ppnt2))->x)
return 1;
if(((ppnt)(ppnt1))->x < ((ppnt)(ppnt2))->x)
return -1;

/* Отрезки считаем открытыми, НЕ включающими свои концы */
if(((ppnt)(ppnt1))->isbegin < ((ppnt)(ppnt2))->isbegin)
return -1;
if(((ppnt)(ppnt1))->isbegin > ((ppnt)(ppnt2))->isbegin)
return 1;

return 0;
}

int compareClosed(const void *ppnt1, const void *ppnt2)
{
if(((ppnt)(ppnt1))->x > ((ppnt)(ppnt2))->x)
return 1;
if(((ppnt)(ppnt1))->x < ((ppnt)(ppnt2))->x)
return -1;

/* Отрезки считаем замкнутыми, включающими свои концы */
if(((ppnt)(ppnt1))->isbegin < ((ppnt)(ppnt2))->isbegin)
return 1;
if(((ppnt)(ppnt1))->isbegin > ((ppnt)(ppnt2))->isbegin)
return -1;

return 0;
}

int main(int argc, char* argv[])
{
FILE *fin;
int N, i;
ppnt p;
double t;

int bestfound, cur;

fin = fopen("in.txt", "rt");

fscanf(fin, "%d", &N);
p = new pnt[N*2];
for(i=0; i<N; i++)
{
fscanf(fin, "%lf", &(p[i*2].x));
fscanf(fin, "%lf", &(p[i*2+1].x));
if(p[i*2].x > p[i*2+1].x)
/* На всякий, вдруг кто начало перед концом напишет... */
{
t = p[i*2].x;
p[i*2].x = p[i*2+1].x;
p[i*2+1].x = t;
}
p[i*2].isbegin = 1;
p[i*2+1].isbegin = 0;
}

fclose(fin);

qsort(p, N*2, sizeof(pnt), compareClosed);

bestfound = cur = 0;
for(i=0; i<N*2; i++)
if(p[i].isbegin)
if(++cur > bestfound) bestfound = cur; else;
else
--cur;

printf("%d-layer overlay(s) found\n", bestfound);

return 0;
}

in.txt

3
1 2
2 3
3 4

Сортировка

startinger — Mon, 08 Dec 2003 08:19:17 +0000

startinger: 2Visitor: Ну поподробнее алгоритм можно? На том же pas'е или просто алгоритмически?

Сортировка

Visitor — Sun, 07 Dec 2003 20:35:00 +0000

Visitor: Да вы чего

Если отрезки змкнутые (включают в себя свои концы), нужно при одинаковой координате первыми ставить начала отрезков, если открытые -- сначала ставить концы. И считать количество пересекшихся -- работает для любых, хоть трижды вырожденных отрезков.

Сортировка

startinger — Sun, 07 Dec 2003 18:54:29 +0000

startinger: Понимаешь, albom, всё бы вроде бы хоршо, но на некоторых
тестах сортировка, которую ты предлагаешь, даёт сбой.
Уже при 6 отрезках есть много вариантов, где одно число
при сортировке становится не на свое место.
Например,
2 7 7 7 3 7 5 11 7 7 1 7
Результат: 1 2 3 7 5 7 7 7 7 7 7 11
Можно еще затестить варианты:
1 7 4 7 6 7 5 7 1 7 2 11
1 10 3 9 9 11 4 7 1 7 3 7
Даже есть варианты, когда получается совсем печально:
1 7 3 9 9 11 4 7 1 7 3 7
Результат: 1 1 3 3 7 4 7 9 9 7 7 11

Искать недочёт пока нет времени, я тут написал вещь
пообъёмнее, но вроде работает корректно. В
сформированном массиве упорядочиваются по убыванию
флаги у одинаковых элементов массива Pos в
процедуре flagsort, которая использует процедуру
invsort-это quicksort по убыванию.
Но это уже по сложности побольше, чем N*LogN, может
быть можно оптимизнуть, ну, например, сделать одну
quicksort, передавая в качестве параметра возраст. или
убывание делать, и сам массив. Или доработать алгоритм
albom'а.

var n,nn,j,i:integer;
pos:array[1..100]of integer;
flag:array[1..100]of shortint;
cur,max:integer;
tl,tr:integer; {границы в сортировке массива flag}

procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=pos[(l+r) DIV 2];
repeat
while pos[i]<x do i:=i+1;
while x<pos[j] do j:=j-1;
if i<=j then
begin
y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

procedure invsort(l,r:integer);
var i,j,x,y:integer;
begin
i:=l; j:=r; x:=flag[(l+r) DIV 2];
repeat
while flag[i]>x do i:=i+1;
while x>flag[j] do j:=j-1;
if i<=j then
begin
y:=flag[i];flag[i]:=flag[j];flag[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then invsort(l,j);
if i<r then invsort(i,r);
end;

procedure flagsort;
var exist:boolean; k:integer;
begin
k:=1; tl:=0; tr:=0;
while k<nn do
begin
exist:=false;
while pos[k]=pos[k+1] do
begin
exist:=true;
if (k>1) and (pos[k]<>pos[k-1]) then tl:=k;
inc(k);
end;
if exist then
begin
if tl=0 then tl:=1;
tr:=k;
invsort(tl,tr);
end;
inc(k);
end;
end;

begin
readln(n);
nn:=n*2;
j:=1;
for i:=1 to n do
begin
readln(pos[j],pos[j+1]);flag[j]:=+1;flag[j+1]:=-1;inc(j,2);
end;
sort(1,nn);
flagsort;
cur:=0;
max:=0;
for i:=1 to nn do
begin
inc(cur,flag[i]);
if cur>max then
max:=cur;
end;

writeln(max);
end.

Сортировка

albom — Fri, 05 Dec 2003 19:02:37 +0000

albom: Ну смотри, в той программе точки сортировались при помощи сранения pos[i].
А что бы считать вырожденные отрезки, этого сравненея недостаточно.
Можно даже ввести функцию:

function less(a,b:integer):boolean;
begin
if pos[a]<pos[b] then less:=true
else if pos[a]>pos[b] then less:=false
else less:=flag[a]>flag[b]
end;

Тогда изменится и процедура sort, вот так:

procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=(l+r) DIV 2;
repeat
while less(i,x) do i:=i+1;
while less(x,j) do j:=j-1;
if i<=j then
begin
y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

Сортировка

startinger — Fri, 05 Dec 2003 04:49:22 +0000
startinger: А если рассмотреть вырожденный отрезок, т.е. точку, то при тестировании алгоритм иногда её считает почему-то, а иногда нет, т.к. сначала добавляет +1, а затем вычитает её приблизительно в том же месте или что-то вроде, т.е. точка засчитывается как 0-отрезок. А нужно считать её за реальный отрезок. Например,
1 11
2 12
3 6
3 3
1 7
3 7
1 2
3 3
Алгоритм должен выдать 7 отрезков.
3 3
Алгоритм должен выдать 1 отрезок.
Как бы поаккуратнее исправить? Просто иногда алгоритм всё-таки считает такие отрезки. Если вспомню тест, выложу.

Сортировка

Visitor — Sat, 22 Nov 2003 09:35:11 +0000
Visitor: Честно говоря тоже не очень понял... но, _должно_ быть что-то вроде:

1.Отсортировали все концы отрезков в массив пар (координата, признак начала отрезка):
2.Двигаемся по етому массиву:
3.==Очередная координата имеет "признак начала"?
4.==Да. Увеличиваем число пересекающихся отрезков
5.====Число пересекающихся отрезков больше последнего запомненного?
6.====Да. Последнее запомненне = (координата, число отрезков)
7.====Нет. Пофих.
8.==Нет. Уменьшаем число пересекающихся отрезков.
9.Пока массив не кончится.

Сортировка

esperanto — Sat, 22 Nov 2003 08:08:02 +0000
esperanto:
Цитата (albom @ 21.11.03, 17:39)
Вот такой вариант:

var n,nn,j,i:integer;
pos:array[1..100]of integer;
flag:array[1..100]of shortint;
cur,max:integer;

procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=pos[(l+r) DIV 2];
repeat
while pos[i]<x do i:=i+1;
while x<pos[j] do j:=j-1;
if i<=j then
begin
y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

begin
readln(n);
nn:=n*2;
j:=1;
for i:=1 to n do
begin
readln(pos[j],pos[j+1]);flag[j]:=+1;flag[j+1]:=-1;inc(j,2);
end;
sort(1,nn);
cur:=0;
max:=0;
for i:=1 to nn do
begin
inc(cur,flag[i]);
if cur>max then
max:=cur;
end;

writeln(max);
end.

Правда тут используется быстрая сортировка, которая в наихудшем случае дает сложность N^2.
Просто не вспомнил запись алгоритма древесной сортировки (с максимальной сложностью N*logN).

как говорил наш преподаватель я не компилятор напишите идею чтобы было понятно

Сортировка

albom — Fri, 21 Nov 2003 18:39:01 +0000
albom: Вот такой вариант:

var n,nn,j,i:integer;
pos:array[1..100]of integer;
flag:array[1..100]of shortint;
cur,max:integer;

procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=pos[(l+r) DIV 2];
repeat
while pos[i]<x do i:=i+1;
while x<pos[j] do j:=j-1;
if i<=j then
begin
y:=pos[i]; pos[i]:=pos[j]; pos[j]:=y;
y:=flag[i];flag[i]:=flag[j];flag[j]:=y;

i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

begin
readln(n);
nn:=n*2;
j:=1;
for i:=1 to n do
begin
readln(pos[j],pos[j+1]);flag[j]:=+1;flag[j+1]:=-1;inc(j,2);
end;
sort(1,nn);
cur:=0;
max:=0;
for i:=1 to nn do
begin
inc(cur,flag[i]);
if cur>max then
max:=cur;
end;

writeln(max);
end.

Правда тут используется быстрая сортировка, которая в наихудшем случае дает сложность N^2.
Просто не вспомнил запись алгоритма древесной сортировки (с максимальной сложностью N*logN).

Сортировка

startinger — Fri, 21 Nov 2003 12:20:36 +0000
startinger: На прямой дано N отрезков с координатами (a[i]; b[i]). 1<=i<=N. Найти максимальное k, для которого существет точка на прямой, покрытая k отрезками. За N*logN операций