1 Отредактировано Rasul Abdulaev (2009-06-25 14:30:51)

Тема: Problem olymp.krsu.edu.kg (Closest Point of Approach)

http://olymp.krsu.edu.kg/GeneralProblem … format=htm
Ya pytalsya reshit s pomochu proizvodnogo.
no ne vyhodit.
vot moi kod

Help plz, Zaranee spasibo

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while (n--) {
        double t,x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4;
        cin>>x1>>y1>>z1>>x2>>y2>>z2>>x3>>y3>>z3>>x4>>y4>>z4;
        x2+=x1; y2+=y1;z2+=z1;
        x4+=x3; y4+=y3;z4+=z3;
        double  c1 = (x2-x1)-(x4-x3) , c2=(y2-y1)-(y4-y3) ,c3  = (z2-z1)-(z4-z3);
        t =(-2.0*x1*c1 + 2*x3*c1   - 2*y1*c2 + 2*y3*c2 -2.0*z1*c3 + 2*z3*c3 )/    (2*c1*c1 +  2*c2*c2 + 2*c3*c3);
        printf("%.3lf\n",t);
    }
}

Re: Problem olymp.krsu.edu.kg (Closest Point of Approach)

Rasul Abdulaev пишет:

http://olymp.krsu.edu.kg/GeneralProblem … format=htm
Vot ya pytalsya ee reshit s pomochu proizvodnogo.

no ne vyhodit.
Pomogite plz. Zaranee spasibo
vot moi kod

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while (n--) {
        double t,x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4;
        cin>>x1>>y1>>z1>>x2>>y2>>z2>>x3>>y3>>z3>>x4>>y4>>z4;
        x2+=x1; y2+=y1;z2+=z1;
        x4+=x3; y4+=y3;z4+=z3;
        double  c1 = (x2-x1)-(x4-x3) , c2=(y2-y1)-(y4-y3) ,c3  = (z2-z1)-(z4-z3);
        t =(-2.0*x1*c1 + 2*x3*c1   - 2*y1*c2 + 2*y3*c2 -2.0*z1*c3 + 2*z3*c3 )/    (2*c1*c1 +  2*c2*c2 + 2*c3*c3);
        printf("%.3lf\n",t);
    }
}

3 Отредактировано KADR (2009-06-25 19:47:25)

Re: Problem olymp.krsu.edu.kg (Closest Point of Approach)

Пусть D(t) - квадрат расстояния между кораблями в момент времени t. Tак как расстояние неотрицательно, то найдя минимум функции D(t) мы автоматически найдем минимум sqrt(D(t)).
X1(t) - x координата первого корабля в момент времени t.
X1(t)=x1 + t*dx1
Аналогично определим X2(t),Y1(t),Y2(t),Z1(t),Z2(t).
D(t)=sqr(X1(t)-X2(t))+sqr(Y1(t)-Y2(t))+sqr(Z1(t)-Z2(t))

Для начала рассмотрим тривиальные случаи:
1) Если D(t) - константа. В таком случае ответ 0.
2) Если D(t) возрастает на [0;+INF). Ответ опять таки 0.

Теперь будем считать, что искомое время t не равно 0.
Есть 2 способа решения этой задачи.

Способ 1:
Заметим, что D(t) - квадратичная функция с аргументом t. Найдя вершину параболы мы как раз и найдем минимум данной функции. Это решение дает точный ответ, но тут очень важно правильно раскрыть скобки и привести уравнение к нужному виду. Подозреваю у Вас ВА как раз из-за ошибки в формулах.

Способ 2:
Очевидно, что расстояние между кораблями вначале будет уменьшаться, а затем возрастать. Следовательно, мы можем применить троичный поиск по времени для поиска минимума функции D(t).

Вот приблизительный код решения(написано в браузере, так что не ручаюсь за то что нету багов):

inline double solve()
{
     double l=0.0,r=1e10;
     while (r-l>eps)
     {
          double t1=(2.0*l+r)/3.0,t2=(l+2.0*r)/3.0;
          if (D(t1)<D(t2)) r=t2; else l=t1;
     }
     return l;
}