|
|
|
|
|
|
|
Вернуться
| 1 Навойчик Андрей Валентинович, 12 ноября 2009 г. 19:10:12 | |
|
Нагин Сергей, спасибо...ща попробуем))))
|
|
|
| 2 Нагин Сергей Юрьевич, 12 ноября 2009 г. 17:27:40 | |
|
Вроде-бы так!
|
|
|
| 3 Нагин Сергей Юрьевич, 12 ноября 2009 г. 17:27:25 | |
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while pol(a[i])<pol(x) do
inc(i);
while pol(x)<pol(a[j]) do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
функция "пол", определяет полярный угол между 1й точкой и точкой Х или Аи!
|
|
|
| 4 Навойчик Андрей Валентинович, 12 ноября 2009 г. 13:18:55 | |
если использовать сортировку пузырьком то это кодится так:
Vect - функция которая определяет знак векторного произведения;
a - массив of ll;
ll=record
x,y:longint;
в а[1] содержится самоя низкая левая координата
for i:=2 to n-1 do
for j:=i+1 to n do
if Vect(a[1],a[i],a[1],a[j])<0 then
Swap(a[i],a[j]);
Как это будет выглядить в QSort???
|
|
|
| 5 Беляев Сергей Николаевич, 12 ноября 2009 г. 11:09:42 | |
|
Более эффективно, как говорит Нвойчик А.В., сортировать не по углу,а по знаку векторного произведения соответствующих векторов. При такой сортировке используется гораздо меньше арифметических операций, в частности не используется извлечение квадратного корня.
|
|
|
| 6 Прищенко Богдан Олегович, 11 ноября 2009 г. 22:19:08 | |
|
Я бы сначала просчитал для каждой точки ее полярный угол относительно точки-образца, завел соответствующий массив, а потом сортировал эти углы. Только при сортировке углов менять не только два угола, но и соответствующую им пару точек.
|
|
|
| 7 Навойчик Андрей Валентинович, 11 ноября 2009 г. 20:49:50 | |
|
*вписать
|
|
|
| 8 Навойчик Андрей Валентинович, 11 ноября 2009 г. 20:49:31 | |
|
все понятно, кроме функции. По идее нужно узнать векторное произведение векторов, и если оно меньше 0, то поменять местами значения a[i] и a[j]...вопрос: как эту функцию вписоть в QSort???
|
|
|
| 9 Нагин Сергей Юрьевич, 11 ноября 2009 г. 18:46:35 | |
|
берешь , ставишь ее первой в списке! Потом пишешь сорт(2,Н) и оно отсортирует! А в сортировке пишешь сравнение по полярному углу, тоесть , не Аи ,а Ф(Аи) , тоесть значение от определенной функции полярного угла!
|
|
|
| 10 Навойчик Андрей Валентинович, 11 ноября 2009 г. 17:25:53 | |
Привет всем!!!
Подскажите, пжл, как при помощи алгоритма быстрой сортировки О(N log N) отсортировать массив координат по полярному углу относительно какой-либо из этих точек (например самой нижней левой)
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
