Выпуклая оболочка

[mirkut]

подскажите как можно посчитать периметр выпуклой  оболочки, расположенной в первой четверти
ПС очень надо
все написать необходимо на Ruby, С++ или Java
а выпуклая оболочка должна строиться  постепенно- т.е. задавать надо постепенно точки
выпуклая оболочка-это многоугольнык, заданный массивом его вершин
известна функция, которая пересчитывает этот массив при вновь прибывшей точке


Исправлено: mirkut, 16:15 9-12-2003


Исправлено: mirkut, 16:20 9-12-2003

[pva]

Вообще-то нужно уточнить, что ты понимаешь под выпуклой оболочкой.
Если это-кривая, заданная параметрически {f(n), g(n)}, то её длина -
Integral(sqrt(df(n)^2+fg(n)^2)), или численно (на С):

const double dn=1;
double length1=0;
for(n=0;n<N;n++) {
 register double df=f[n]-f[n-1];
 register double dg=g[n]-g[n-1];
 length1+=sqrt(df*df+dg*dg)*dn;
}
cout<<"length1="<<length1<<endl;

или, если как функция, то Integral(sqrt(1+df(n)^2)), или

const double dn=1;
double length1=0;
for(n=0;n<N;n++) {
 register double df=f[n]-f[n-1];
 length1+=sqrt(df*df+1)*dn;
}
cout<<"length1="<<length1<<endl;