e-olymp 9081. Автомобілі

30/11/2019 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$, $v_2$, $v_3$, $t_1$, $t_2$, $t_3$. Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

#include <iostream>
using namespace std;
 
int main() {
    int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
    int t1, t2, t3; // Час, який вони їхали
    int s1, s2, s3; // І відстань
    int max_; // Також, змінну, де буде зберігатися максимальна відстань
    cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія
    cin >> v2 >> t2; 
    cin >> v3 >> t3;
    s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
    s2 = v2 * t2; 
    s3 = v3 * t3;
    max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань
    if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
        cout << "1 "; // Виводимо номер відповідного водія
    if ( s2 == max_ )
        cout << "2 ";
    if ( s3 == max_ )
        cout << 3;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія

cin >> v2 >> t2;

cin >> v3 >> t3;

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

cout << "1 "; // Виводимо номер відповідного водія

if ( s2 == max_ )

cout << "2 ";

if ( s3 == max_ )

cout << 3;

return 0;

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$. Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.

Посилання

Related Images:

e-olymp 49. Кот учёный

09/05/2018 by Костя Григорян

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

Входные данные

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

Выходные данные

Вывести день, на который у кота появится чувство голода.

Тесты

Входные данные	Выходные данные
[latex]4\, 4\, 2[/latex]	[latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex]	[latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex]	[latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

Код программы

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int l, n, k, count=0;
    cin >> l >> n >> k;
    for(int i=0; i<n; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)
            count++;
        else
        {
            int a, b, c;
            int deltaX=x2-x1;
            int deltaY=y2-y1;
            a=deltaY;
            b=-deltaX;
            c=y1*deltaX-x1*deltaY;
            if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))
                count++;
        }
    }
    cout << count/k+1 << endl; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int l, n, k, count=0;

cin >> l >> n >> k;

for(int i=0; i<n; i++)

{

int x1, y1, x2, y2;

cin >> x1 >> y1 >> x2 >> y2;

if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)

count++;

else

{

int a, b, c;

int deltaX=x2-x1;

int deltaY=y2-y1;

a=deltaY;

b=-deltaX;

c=y1*deltaX-x1*deltaY;

if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))

count++;

}

cout << count/k+1 << endl;

return 0;

}

Решение задачи

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 74. Паук и муха — 2

16/12/2017 by Алиса Ворохта

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится? Известно, что паук может передвигаться только по поверхности комнаты или же спускаться на паутине с потолка на пол, но только под прямым углом.

Входные данные

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

Выходные данные

Одно число – расстояние, на которое переместится паук, посчитанное с точностью до 2-х знаков после запятой.

Тесты

Входные данные								Выходные данные
[latex]A[/latex]	[latex]B[/latex]	[latex]C[/latex]	[latex]X1[/latex]	[latex]Y1[/latex]	[latex]X2[/latex]	[latex]Y2[/latex]	[latex]Z2[/latex]	[latex]S[/latex]
[latex]4[/latex]	[latex]7[/latex]	[latex]3[/latex]	[latex]2[/latex]	[latex]1[/latex]	[latex]3[/latex]	[latex]7[/latex]	[latex]2[/latex]	[latex]8.06[/latex]
[latex]145[/latex]	[latex]26[/latex]	[latex]306[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]0[/latex]	[latex]305[/latex]	[latex]309.34[/latex]
[latex]26[/latex]	[latex]18[/latex]	[latex]53[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]24[/latex]	[latex]1[/latex]	[latex]53[/latex]	[latex]58.52[/latex]
[latex]89[/latex]	[latex]89[/latex]	[latex]189[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]89[/latex]	[latex]16[/latex]	[latex]70.77[/latex]
[latex]18[/latex]	[latex]26[/latex]	[latex]145[/latex]	[latex]14[/latex]	[latex]2[/latex]	[latex]17[/latex]	[latex]26[/latex]	[latex]141[/latex]	[latex]147.14[/latex]

Код программы

#include <iostream>
#include <cmath> //подключаем для возможности извлечения корня
#include <iomanip> //подключаем, чтобы округлить до определенного количества знаков
using namespace std;
 
double distance(long long X1, long long Y1, long long X2, long long Y2) 
{
    return sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));
}
int main() {
    long long A, B, C, X1, X2, Y1, Y2, Z2;
    double S = 1000000000;
    cin >> A >> B >> C >> X1 >> Y1 >> X2 >> Y2 >> Z2;
    if (Z2 == 0)
    {
        S = distance(X1, Y1, X2, Y2);
    }
    else
    {
        if (X2 == 0)
        {
            S = min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));
            S = min(S, distance(X1, Y1, Y2 - B, B + Z2));
        }
        if (X2 == A)
        {
            S = min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));
            S = min(S, distance(X1, Y1, A + B - Y2, Z2 + B));
        }
        if (Y2 == 0)
        {
            S = min(S, distance(X1, Y1, X2, -Z2));
            S = min(S, distance(X1, Y1, -Z2, -X2));
            S = min(S, distance(X1, Y1, A + Z2, X2 - A));
        }
        if (Y2 == B)
        {
            S = min(S, distance(X1, Y1, X2, Z2 + B));
            S = min(S, distance(X1, Y1, -Z2, X2 + B));
            S = min(S, distance(X1, Y1, A + Z2, B + A - X2));
        }
        if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))
        {
            S = min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));
            S = min(S, distance(X1, Y1, X2, 2*B - Y2 + C));
            S = min(S, distance(X1, Y1, -X2 - C, Y2));
            S = min(S, distance(X1, Y1, 2*A - X2 + C, Y2));
            S = min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));
            S = min(S, distance(X1, Y1, A + C + Y2, X2 - A));
            S = min(S, distance(X1, Y1, -C - Y2, -X2));
            S = min(S, distance(X1, Y1, Y2 - B - C, B + X2));
            S = min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));
            S = min(S, distance(X1, Y1, Y2 - B, B + C + X2));
            S = min(S, distance(X1, Y1, -Y2, -C - X2));
            S = min(S, distance(X1, Y1, A + Y2, -A - C + X2));
        }
    }
    cout << fixed << setprecision(2) << S;
    return 0;
}

#include <iostream>

#include <cmath> //подключаем для возможности извлечения корня

#include <iomanip> //подключаем, чтобы округлить до определенного количества знаков

using namespace std;

double distance(long long X1, long long Y1, long long X2, long long Y2)

{

return sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));

}

int main() {

long long A, B, C, X1, X2, Y1, Y2, Z2;

double S = 1000000000;

cin >> A >> B >> C >> X1 >> Y1 >> X2 >> Y2 >> Z2;

if (Z2 == 0)

{

S = distance(X1, Y1, X2, Y2);

}

else

{

if (X2 == 0)

{

S = min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));

S = min(S, distance(X1, Y1, Y2 - B, B + Z2));

}

if (X2 == A)

{

S = min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));

S = min(S, distance(X1, Y1, A + B - Y2, Z2 + B));

}

if (Y2 == 0)

{

S = min(S, distance(X1, Y1, X2, -Z2));

S = min(S, distance(X1, Y1, -Z2, -X2));

S = min(S, distance(X1, Y1, A + Z2, X2 - A));

}

if (Y2 == B)

{

S = min(S, distance(X1, Y1, X2, Z2 + B));

S = min(S, distance(X1, Y1, -Z2, X2 + B));

S = min(S, distance(X1, Y1, A + Z2, B + A - X2));

}

if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))

{

S = min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));

S = min(S, distance(X1, Y1, X2, 2*B - Y2 + C));

S = min(S, distance(X1, Y1, -X2 - C, Y2));

S = min(S, distance(X1, Y1, 2*A - X2 + C, Y2));

S = min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));

S = min(S, distance(X1, Y1, A + C + Y2, X2 - A));

S = min(S, distance(X1, Y1, -C - Y2, -X2));

S = min(S, distance(X1, Y1, Y2 - B - C, B + X2));

S = min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));

S = min(S, distance(X1, Y1, Y2 - B, B + C + X2));

S = min(S, distance(X1, Y1, -Y2, -C - X2));

S = min(S, distance(X1, Y1, A + Y2, -A - C + X2));

}

cout << fixed << setprecision(2) << S;

return 0;

}

Решение задачи

Данная задача решается с помощью «разверток» комнаты: переход от трёхмерного пространства к двумерному.
Вид комнаты:

Рассмотрим такие случаи:

Паук находится на полу ([latex]Z_2 = 0[/latex]);
Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex] с помощью функции [latex]distance[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

Паук ползет по этой стенке, затем по полу. Тогда развертка будет такой:
Паук ползет через ближнюю к нам стенку и по полу. Тогда развертка следующая:
Аналогичен предыдущему случаю, только через дальнюю от нас стенку.

По этим разверткам мы можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex]. Если же паук находится в одном из углов комнаты, то мы находим наименьшее расстояние из двух вариантов развертки.
Когда же паук сидит на потолке, не соприкасаясь ни с одной из стенок, у него есть 13 вариантов:

Паук спускается с потолка на паутине, затем ползет точно так же, как и в самом первом случае.
Паук ползет по потолку, по одной из стенок и по полу. Тогда развертка будет выглядеть следующим образом (потолок можно развернуть в 4 стороны — отсюда 4 случая):
Паук ползет по потолку, а затем по двум соседним стенкам и по полу. Таких случаев 8, поскольку порядок следования стенок, по которым тот ползет, также важен. Развертка одного из них:

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex].

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

Related Images:

Ю2.30. Расстояние между отрезками

12/10/2016 by Тимур Фирсов

Задача

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Найти расстояние между двумя между двумя произвольно заданными на плоскости отрезками [latex]AB[/latex] и [latex]CD[/latex].

Входные данные:

Координаты концов первого отрезка [latex]A[/latex] [latex](x_a, y_a)[/latex], [latex]B[/latex] [latex](x_b, y_b)[/latex].
Координаты концов второго отрезка [latex]C[/latex] [latex](x_c, y_c)[/latex], [latex]D[/latex] [latex](x_d, y_d)[/latex].

Выходные данные:

Расстояние между отрезками [latex]min[/latex].

Тесты

	Входные данные								Выходные данные
№	[latex]x_a[/latex]	[latex]y_a[/latex]	[latex]x_b[/latex]	[latex]y_b[/latex]	[latex]x_c[/latex]	[latex]y_c[/latex]	[latex]x_d[/latex]	[latex]y_d[/latex]	[latex]min[/latex]
1	1	1	2	1	3	1	4	1	1
2	0	0	5	5	1	1	2	2	0
3	0	1	3	3	5	3	6	4	2
4	0	0	7	0	0	8	5	3	3
5	5	5	10	10	5	9	6	12	2.8284
6	2	1	3	5	0	0	0	5	2
7	-3	0	3	0	0	-3	0	3	0

Код программы

#include <iostream>
#include <cmath>
using namespace std;

double ras(double x1, double y1, double x2, double y2, double x3, double y3){
    double k,d;
    if(x1==x2){ //Если отрезок вертикальный - меняем местами координаты каждой точки.
    swap(x1, y1);
    swap(x2, y2);
    swap(x3, y3);
    }
    k=(y1-y2)/(x1-x2);//Ищем коэффициенты уравнения прямой, которому принадлежит данный отрезок.
    d=y1-k*x1;
    double xz=(x3*x2-x3*x1+y2*y3-y1*y3+y1*d-y2*d)/(k*y2-k*y1+x2-x1);
    double dl=-1;
    if((xz<=x2&&xz>=x1)||(xz<=x1&&xz>=x2)) dl=sqrt((x3-xz)*(x3-xz)+(y3-xz*k-d)*(y3-xz*k-d));//Проверим лежит ли основание высоты на отрезке.
    return dl;
}
int main() {
    double xa, xb, ya, yb, xc, xd, yc, yd, dl, dl1, dl2, dl3, dl4, min=-1,o,o1,o2,t=-2,s=-2;
    cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd;
    o=(xb-xa)*(-yd+yc)-(yb-ya)*(-xd+xc);
    o1=(xb-xa)*(yc-ya)-(yb-ya)*(xc-xa);
    o2=(-yd+yc)*(xc-xa)-(-xd+xc)*(yc-ya);
    if(o!=0){
        t=o1/o;
        s=o2/o;
    }
    if((t>=0&&s>=0)&&(t<=1&&s<=1))min=0;//Проверим пересекаются ли отрезки.
    else{ 
        //Найдём наименьшую высоту опущенную из конца одного отрезка на другой.
        dl1=ras(xa,ya,xb,yb,xc,yc);
        min=dl1;
        dl2=ras(xa,ya,xb,yb,xd,yd);
        if((dl2<min&&dl2!=-1)||min==-1)min=dl2;
        dl3=ras(xc,yc,xd,yd,xa,ya);
        if((dl3<min&&dl3!=-1)||min==-1)min=dl3;
        dl4=ras(xc,yc,xd,yd,xb,yb);
        if((dl4<min&&dl4!=-1)||min==-1)min=dl4;
        if(min==-1){
            //В случае, если невозможно опустить высоту найдём минимальное расстояние между точками.
            dl1=sqrt((xa-xc)*(xa-xc)+(ya-yc)*(ya-yc));
            min=dl1;
            dl2=sqrt((xb-xd)*(xb-xd)+(yb-yd)*(yb-yd));
            if(dl2<min)min=dl2;
            dl3=sqrt((xb-xc)*(xb-xc)+(yb-yc)*(yb-yc));
            if(dl3<min)min=dl3;
            dl4=sqrt((xa-xd)*(xa-xd)+(ya-yd)*(ya-yd));
            if(dl4<min)min=dl4;
        }
    }
    cout<<min;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double ras(double x1, double y1, double x2, double y2, double x3, double y3){

double k,d;

if(x1==x2){ //Если отрезок вертикальный - меняем местами координаты каждой точки.

swap(x1, y1);

swap(x2, y2);

swap(x3, y3);

}

k=(y1-y2)/(x1-x2);//Ищем коэффициенты уравнения прямой, которому принадлежит данный отрезок.

d=y1-k*x1;

double xz=(x3*x2-x3*x1+y2*y3-y1*y3+y1*d-y2*d)/(k*y2-k*y1+x2-x1);

double dl=-1;

if((xz<=x2&&xz>=x1)||(xz<=x1&&xz>=x2)) dl=sqrt((x3-xz)*(x3-xz)+(y3-xz*k-d)*(y3-xz*k-d));//Проверим лежит ли основание высоты на отрезке.

return dl;

}

int main() {

double xa, xb, ya, yb, xc, xd, yc, yd, dl, dl1, dl2, dl3, dl4, min=-1,o,o1,o2,t=-2,s=-2;

cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd;

o=(xb-xa)*(-yd+yc)-(yb-ya)*(-xd+xc);

o1=(xb-xa)*(yc-ya)-(yb-ya)*(xc-xa);

o2=(-yd+yc)*(xc-xa)-(-xd+xc)*(yc-ya);

if(o!=0){

t=o1/o;

s=o2/o;

}

if((t>=0&&s>=0)&&(t<=1&&s<=1))min=0;//Проверим пересекаются ли отрезки.

else{

//Найдём наименьшую высоту опущенную из конца одного отрезка на другой.

dl1=ras(xa,ya,xb,yb,xc,yc);

min=dl1;

dl2=ras(xa,ya,xb,yb,xd,yd);

if((dl2<min&&dl2!=-1)||min==-1)min=dl2;

dl3=ras(xc,yc,xd,yd,xa,ya);

if((dl3<min&&dl3!=-1)||min==-1)min=dl3;

dl4=ras(xc,yc,xd,yd,xb,yb);

if((dl4<min&&dl4!=-1)||min==-1)min=dl4;

if(min==-1){

//В случае, если невозможно опустить высоту найдём минимальное расстояние между точками.

dl1=sqrt((xa-xc)*(xa-xc)+(ya-yc)*(ya-yc));

min=dl1;

dl2=sqrt((xb-xd)*(xb-xd)+(yb-yd)*(yb-yd));

if(dl2<min)min=dl2;

dl3=sqrt((xb-xc)*(xb-xc)+(yb-yc)*(yb-yc));

if(dl3<min)min=dl3;

dl4=sqrt((xa-xd)*(xa-xd)+(ya-yd)*(ya-yd));

if(dl4<min)min=dl4;

}

cout<<min;

return 0;

}

Решение

Для начала проверим не пересекаются ли отрезки. Пусть для отрезка [latex]AB[/latex] [latex]x=t(x_b-x_a)+x_a[/latex], [latex]y=t(y_b-y_a)+y_a[/latex], а для [latex]CD[/latex] [latex]x=s(x_d-x_c)+x_c[/latex], [latex]y=s(y_d-y_c)+y_c[/latex] (где [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex] ). Если отрезки пересекаются, то выполняются равенства: [latex]t(x_b-x_a)-s(x_d-x_c)=x_c-x_a[/latex] и [latex]t(y_b-y_a)-s(y_d-y_c)=y_c-y_a[/latex]. Полученную систему уравнений решим методом Крамера:
[latex]\Delta =\begin{pmatrix} x_b-x_a & \quad x_c-x_d \\ y_b-y_a & \quad y_c-y_d \end{pmatrix}=(x_b-x_a)(y_c-y_d)-(y_b-y_a)(x_c-x_d)[/latex] [latex]\Delta _1=\begin{pmatrix} x_{ b }-x_{ a } & \quad x_{ c }-x_{ a } \\ y_{ b }-y_{ a } & \quad y_{ c }-y_{ a } \end{pmatrix}=(x_b-x_a)(y_c-y_a)-(y_b-y_a)(x_c-x_a)[/latex] [latex]\Delta _2=\begin{pmatrix} x_{ c }-x_{ a } & \quad x_{ c }-x_{ d } \\ y_{ c }-y_{ a } & \quad y_{ c }-y_{ d } \end{pmatrix}=(y_c-y_d)(x_c-x_a)-(x_c-x_d)(y_c-y_a)[/latex].
Тогда [latex]t=\frac { \Delta_1 }{ \Delta } [/latex], а [latex]s=\frac { \Delta_2 }{ \Delta } [/latex]. Если [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex], а [latex]\Delta \neq 0[/latex], то отрезки пересекаются и расстояние между ними [latex]min[/latex] равно [latex]0[/latex], иначе с каждого конца отрезка попытаемся опустить высоту на противоположный. Если отрезок, на который опускаем высоту вертикальный, то поменяем местами координаты каждого конца отрезка и точки, с которой опускаем высоту (таким образом сохраним расстояние между точкой и отрезком, а отрезок станет горизонтальным). Пусть [latex]k[/latex] и [latex]d[/latex] — коэффициенты уравнения прямой, на которую опущена эта высота. Основание высоты будет находится на прямой в точке [latex]Z[/latex], координаты [latex]Z[/latex] [latex](x_z, y_z)[/latex] можно найти по формуле [latex]y_z=kx_z+d[/latex]. Поскольку высота перпендикулярна отрезку — скалярное произведение их векторов равно [latex]0[/latex]. Тогда [latex](x_2-x_1)(x_3-x_z)+(y_2-y_1)(y_3-y_z)=0[/latex], соответственно [latex]x_z=\frac { x_3x_2-x_3x_1+y_2y_3-y_1y_3+y_1d-y_2d }{ ky_2-ky_1+x_2-x_1 } [/latex] (где [latex](x_3, y_3)[/latex] — координаты точки, с которой была опущена высота, [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] — координаты концов отрезка, принадлежащего прямой на которую опущена высота). Вычислим длину [latex]dl[/latex] каждой высоты, основание которой принадлежит одному из данных отрезков: [latex]dl=\sqrt { {(x_3-x_z)}^{2}+{(y_3-x_zk-d)}^{2} }[/latex](где [latex] (x_3, y_3)[/latex] — координаты точки, с которой была опущена высота). Минимальная длина высоты и будет наименьшим расстоянием между отрезками. В случае, если невозможно опустить высоты из одного отрезка на другой: расстояние между ними будет равно минимальному расстоянию между концами двух отрезков [latex]min=\sqrt { {( x_1-x_3) }^{ 2 }+{ (y_1-y_3) }^{ 2 } }[/latex] (где [latex](x_1, y_1)[/latex] — координаты одного из концов первого отрезка, а [latex](x_3, y_3)[/latex] — координаты одного из концов второго отрезка) .

Ссылки

Код программы
Условие задачи (страница 32).

Related Images:

Ю 4.37

23/11/2014 by Байков Дмитро

Задача

Автостоп-2. Из пункта А в пункт В, между которыми [latex]s[/latex] км, выехал велосипедист с постоянной скоростью [latex]v_{0}[/latex] км/ч. Навстречу ему — из пункта В — другой путешественник решил добраться «автостопом» — на разных видах попутного транспорта. Перед каждым участком он [latex]\tau _{i}[/latex] минут «голосует», ожидая попутного транспорта, затем движется [latex]t _{i}[/latex] часов со скоростью [latex]v _{i}[/latex] км/час ( величины [latex]\tau _{i}, t _{i}, v _{i}, i=1,2,\ldots,n[/latex] заданы в соответствующих массивах). Через какое время после старта и на каком расстоянии от пункта А путники встретятся?

Тесты

s	[latex]v_{0}[/latex]	n	[latex]\tau _{i}[/latex]	[latex]t _{i}[/latex]	[latex]v _{i}[/latex]	place, км	time, ч	Комментарий
100.0	30.0	1	60.0	1.0	40.0	60.0	2.0	Пройден
100.0	10.0	1	0.0	1.0	40.0	Путники не доехали до места встречи		Не пройден
130.0	15.0	2	0.0 3.0	1.0 2.6	40.0 33.3	2.587267	38.809006	Пройден

Код программы

#include <iostream>
using namespace std;

int main() 
{
	int n; cin >> n;
	double  place, time, wait [n], mov [n], speed [n], s, v0, timee = 0.0, 
	delta, ss = 0.0, dist = 0.0;
	cin >> s; cin >> v0;
	for (int i = 0 ; i < n; i++)
	{
		cin >> wait[i];
		wait[i] /= 60;
	}
	for (int i = 0 ; i < n; i++)
	{
		cin >> mov[i];
	}
	for (int i = 0 ; i < n; i++)
	{
		cin >> speed[i];
	}
	
	for (int i = 0 ; i < n; i++)
	{
		delta = v0 * wait[i] ;
		timee += wait[i] ;
		if ( s <= delta ) 
		{
			time = s / v0; 
			place = s;
			printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);
			break;
		}
		ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];
		if (ss >= s )
		{
			time = ( s - dist - delta ) / ( v0 + speed[i]) + timee ;  
			place = time * v0 ; 
			printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);
			break;
		} 
		else
		{
			dist = ss;
		}
		timee += mov[i];
	}
	if ( ss < s ) printf("Путники не доехали до места встречи"); 
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n; cin >> n;

double place, time, wait [n], mov [n], speed [n], s, v0, timee = 0.0,

delta, ss = 0.0, dist = 0.0;

cin >> s; cin >> v0;

for (int i = 0 ; i < n; i++)

{

cin >> wait[i];

wait[i] /= 60;

}

for (int i = 0 ; i < n; i++)

{

cin >> mov[i];

}

for (int i = 0 ; i < n; i++)

{

cin >> speed[i];

}

for (int i = 0 ; i < n; i++)

{

delta = v0 * wait[i] ;

timee += wait[i] ;

if ( s <= delta )

{

time = s / v0;

place = s;

printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);

break;

}

ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];

if (ss >= s )

{

time = ( s - dist - delta ) / ( v0 + speed[i]) + timee ;

place = time * v0 ;

printf("Путники встретятся через %lf часов на расстоянии в %lf км от точки А", time, place);

break;

}

else

{

dist = ss;

}

timee += mov[i];

}

if ( ss < s ) printf("Путники не доехали до места встречи");

return 0;

}

Вначале программы вводим во входной поток и считываем данные. Далее, в цикле, проверяем несколько условий, таких как:

Пока второй ждал — первый уже проехал весь путь.
Если после i-ого этапа (т.е. после ожидания транспортного средства, поездки на нем) сумма пройденного пути второго и первого путника больше, чем весь путь.

Далее высчитываем само место и время встречи.
В конце программы, за циклом, проверяем каков общий пройденный путь двух путников и если он меньше всего пути, то выводим сообщение, что они так и не встретились.

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Hitchhiking
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		double  place, time, delta, timee = 0.0, ss = 0.0, dist = 0.0;
		double[] wait = new double[n], mov = new double[n], speed = new double[n];
		double s = in.nextDouble();
		double v0 = in.nextDouble();
		for (int i = 0; i < n; i++)
			wait[i] = in.nextDouble() / 60;
		for (int i = 0; i < n; i++)
			mov[i] = in.nextDouble();
		for (int i = 0; i < n; i++)
			speed[i] = in.nextDouble();
		for (int i = 0; i < n; i++)
		{
			delta = v0 * wait[i] ;
			timee += wait[i] ;
			if (s <= delta) 
			{
				time = s / v0; 
				place = s;
				System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");
				break;
			}
			ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];
			if (ss >= s)
			{
				time = (s - dist - delta) / (v0 + speed[i]) + timee;  
				place = time * v0 ; 
				System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");
				break;
			} 
			else
			{
				dist = ss;
			}
			timee += mov[i];
		}
		if (ss < s) System.out.printf("Путники не доехали до места встречи"); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Hitchhiking

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

double place, time, delta, timee = 0.0, ss = 0.0, dist = 0.0;

double[] wait = new double[n], mov = new double[n], speed = new double[n];

double s = in.nextDouble();

double v0 = in.nextDouble();

for (int i = 0; i < n; i++)

wait[i] = in.nextDouble() / 60;

for (int i = 0; i < n; i++)

mov[i] = in.nextDouble();

for (int i = 0; i < n; i++)

speed[i] = in.nextDouble();

for (int i = 0; i < n; i++)

{

delta = v0 * wait[i] ;

timee += wait[i] ;

if (s <= delta)

{

time = s / v0;

place = s;

System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");

break;

}

ss += v0 * mov[i] + v0 * wait[i] + mov[i] * speed[i];

if (ss >= s)

{

time = (s - dist - delta) / (v0 + speed[i]) + timee;

place = time * v0 ;

System.out.printf("Путники встретятся через " + time + " часов на расстоянии в " + place + " км от точки А");

break;

}

else

{

dist = ss;

}

timee += mov[i];

}

if (ss < s) System.out.printf("Путники не доехали до места встречи");

}

Related Images:

Ю3.8

17/10/2014 by Карташов Денис Геннадійович

«Отскоки»

Задача: Материальная точка бросается на горизонтальную плоскость со скоростью [latex]V[/latex] и под углом [latex]\alpha[/latex] к ней ( плоскости ). При каждом ударе о плоскость, кинетическая энергия точи уменьшается в [latex]\beta[/latex] раз. Найти абсциссы первых [latex]n[/latex] точек касания. Сопротивлением воздуха пренебречь.

По умолчанию примем количество интересующих нас отскоков равным 3.

[latex]V[/latex](speed)[latex]m/c[/latex]	[latex]\alpha[/latex](corner)	[latex]\beta[/latex]	Первая координата	Вторая координата	Третья координата	Комментарий
10	15	2	5.09858	7.64787	8.92252	Тест пройден
8	30	4	5.65184	7.06480	7.41804	Тест пройден
27	45	3	74.3373	99.1164	107.376	Тест пройден
17	35	3	27.6926	36.9234	40.0004	Тест пройден
13	0	5	0.00000	0.00000	0.00000	Тест пройден

Замечание:

По неизвестной мне причине (думаю на погрешность округления) [latex]sin( \pi)[/latex] при вычислениях равен 1.24879e-15.

Исходный код:

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
   double speed, corner, twice_corner, B, Sum=0, sqrspeed;  // Ввод переменных типа double.
   const double g=9.80665;                                  // Ввод неизвестной компьютеру константы.
   int num;                                                 //Ввод числа отскоков, которые будут нас интересовать.
   cout <<" Первое число - это скорость,"
        <<endl
        <<" второе - угол,"
        <<endl
	    <<" третье - коэффициент уменьшения кинетической энергии,"
	    <<endl
	    <<" четвертое - это число точек касания с плоскостью."
	    <<endl;
	
    cin >> speed;             //Ввод значений переменных.    
    cin >> corner;
    cin >> B;
    cin >> num;
    if(speed<0||corner>90||corner<0||B<=0||num<=0){ // Проверка на недопустимые ситуации
		cout<<" Похоже произошла ошибка."<<endl<<" Пожалуйста, введите данные повторно."<<endl;
		return 1;
	} 
    twice_corner=2*M_PI*corner/180;            // Перевод величины угла из градусов в радианы и нахождение двойного угла
    sqrspeed=speed*speed;                      // Вычисление квадрата скорости точки
    for(int i=1;i<=num;i++){                   // Цикл: вычисление координат по формуле и вывод результатов.
   	    double x;
   	    x=sqrspeed*sin(twice_corner)/g;
   	    Sum+=x;
   	    cout<<"Координата точки номер " << i <<" = " << Sum <<endl;
   	    sqrspeed/=B;
   }
	return 0;                               //Конец
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double speed, corner, twice_corner, B, Sum=0, sqrspeed; // Ввод переменных типа double.

const double g=9.80665; // Ввод неизвестной компьютеру константы.

int num; //Ввод числа отскоков, которые будут нас интересовать.

cout <<" Первое число - это скорость,"

<<endl

<<" второе - угол,"

<<endl

<<" третье - коэффициент уменьшения кинетической энергии,"

<<endl

<<" четвертое - это число точек касания с плоскостью."

<<endl;

cin >> speed; //Ввод значений переменных.

cin >> corner;

cin >> B;

cin >> num;

if(speed<0||corner>90||corner<0||B<=0||num<=0){ // Проверка на недопустимые ситуации

cout<<" Похоже произошла ошибка."<<endl<<" Пожалуйста, введите данные повторно."<<endl;

return 1;

}

twice_corner=2*M_PI*corner/180; // Перевод величины угла из градусов в радианы и нахождение двойного угла

sqrspeed=speed*speed; // Вычисление квадрата скорости точки

for(int i=1;i<=num;i++){ // Цикл: вычисление координат по формуле и вывод результатов.

double x;

x=sqrspeed*sin(twice_corner)/g;

Sum+=x;

cout<<"Координата точки номер " << i <<" = " << Sum <<endl;

sqrspeed/=B;

}

return 0; //Конец

}

Для решения задачи необходимо вспомнить уроки физики в начале десятого класса, а именно главу о движении под углом к горизонту. Воспользуемся формулой расстояния полета материальной точки [latex]S=\frac{V^2sin(2\alpha) }{g}[/latex] . По условию задачи сказано, что кинетическая энергия уменьшается при каждом отскоке в [latex]\beta[/latex] раз. Если рассмотреть формулу кинетической энергии: [latex]E_{k}=\frac{ mV^2 }{2}[/latex]- можно заметить, что [latex] m[/latex] (масса) является константой, значит изменяться может только [latex]V^2[/latex] (скорость тела в квадрате). Если условится, что материальная точка начинает движение в начале координат, то координата первого отскока будет равна [latex]S[/latex], второй — [latex]S+S_{1}[/latex], третьей — [latex]S+S_{1}+S_{2}[/latex], n-ой — [latex]S+…+S_{n-1}[/latex].

Алгоритм:

Объявление переменных и константы(ускорение свободного падения).
Вывод поясняющей информации.
Ввод значений переменных.
Проверка недопустимых ситуаций:
- Проверка угла: значения угла выше 90 градусов или отрицательное значение противоречат условию задачи.
- Проверка скорости: отрицательное значение будет означать движение в противоположную интересующей нас сторону.
- Проверка коэффициента уменьшения кинетической энергии: это число должно быть хотя бы положительным.
- Проверка числа интересующих нас отскоков: это должно быть натуральное число.
Вычисление вспомогательных величин (двойной угол, скорость в квадрате).
Создание вычислительного цикла.
- Вывод значений.
Окончание работы.

Ссылка на Ideone.

Related Images:

Ю 2.31

21/09/2014 by Байков Дмитро

Задача

График движения путников к задаче Ю2.31

Встреча. Из пункта А в пункт В выехал велосипедист со скоростью [latex]v_{0} [/latex] км/час. Одновременно навстречу ему из пункта В двинулся «автостопом» другой путник.[latex]s_{1} [/latex] м он двигался со скоростью [latex]v_{1} [/latex] м/час, [latex]s_{2} [/latex] м — со скоростью [latex]v_{0} [/latex] км/час, [latex]s_{3} [/latex] м — со скоростью [latex]v_{3} [/latex] км/час. Через сколько часов после старта и в какой точке путники встретились?

Тесты

v0, км/час	v1, м/час	v3, км/час	s1, м	s2, м	s3, м	place, км	time, час	Комментарии
40	15000	10	20000	40000	40000	66.667	1.667	Пройден (встреча на первом промежутке)
10	5000	60	10000	60000	30000	55.0	5.5	Пройден (встреча на первом промежутке)
8	5000	30	10000	10000	80000	37.368	4.671	Пройден (встреча на первом промежутке)
-300	30000	23333	22222	5454	555.1	Неправильно введены данные		Не пройден
10	2222	3333	0	-4444	11.6	Неправильно введены данные		Не пройден

Код программы:

#include <iostream>
#include <math.h>
    int main() 
    {
        double v0, v1, v3, place, ss, s1, s2, s3, time, t1, t2, t3 ; //Описание переменных для хранения входных данных.//
        scanf("%lf%lf%lf%lf%lf%lf", & v0, & v1, & v3, & s1, & s2, & s3) ; //Чтение из стандартного потока ввода.//
        if ( ( v0 > 0 ) && ( v1 > 0 ) && ( v3 > 0 ) && ( s1 >= 0 ) && ( s2 >= 0 ) && ( s3 >= 0 ) )  //Критерии ввода данных.//
            {
                s1 *= 0.001 ; v1 *= 0.001 ; s2 *= 0.001 ; s3 *= 0.001 ; //Перевод единиц в систему СИ. (м --> км, м/час --> км/час) //
                ss = s1 + s2 + s3 ; //Найдем весь путь//
                t1 = s1 / v1 ; t2 = s2 / v0 ; t3 = s3 / v3 ; //Найдем время за которое второй путник преодолевает каждую часть пути//
                if ( ( ss - t1 * v0 - s1 ) <= 0 ) //Условие встречи двух путников на первом промежутке пути//
                {
                    time = ss / ( v0 + v1 ) ;  //Нахождение времени встречи//
                    place = time * v0 ;     //Нахождение места встречи// 
                    printf("Путники встретились на расстоянии %5.3lf км от пункта В через %5.3lf часов после старта", place, time) ; //Вывод конечного результата.//
                } 
                else
                {
                    if ( ( ss - ( t2 + t1 ) * v0 - s1 - s2 ) <=0 ) //Условие встречи двух путников на втором промежутке пути//
                    {
                        time = ( ss - s1 - ( v0 * t1 ) ) / ( v0 + v0 ) ; //Нахождение времени встречи//
                        place = ( t1 + time ) * v0 ; //Нахождение места встречи// 
                        printf("Путники встретились на расстоянии %5.3lf км от пункта В через %5.3lf часов после старта", place, time+t1) ; //Вывод конечного результата.//
                    }
                    else 
                    {
                        if ( ( ss - ( t2 + t1 + t3 ) * v0 - s1 - s2 - s3 ) <= 0 ) //Условие встречи двух путников на третем промежутке пути//
                        {
                            time = ( ss - s1 - s2 - ( v0 * ( t2 + t1 ) ) ) / ( v0 + v3 ) ; //Нахождение времени встречи//
                            place = ( t1 + t2 + time ) * v0 ; //Нахождение места встречи// 
                            printf("Путники встретились на расстоянии %5.3lf км от пункта A через %5.3lf часов после старта", place, time+t1+t2) ; //Вывод конечного результата.//
                        }
                    }
                }
            }
            else 
            {
                printf("Неправильно введены данные"); //Вывод оповещения о неправильном вводе данных (при несоответствии начальным критериям).
            }
            return 0;
    }

#include <iostream>

#include <math.h>

int main()

{

double v0, v1, v3, place, ss, s1, s2, s3, time, t1, t2, t3 ; //Описание переменных для хранения входных данных.//

scanf("%lf%lf%lf%lf%lf%lf", & v0, & v1, & v3, & s1, & s2, & s3) ; //Чтение из стандартного потока ввода.//

if ( ( v0 > 0 ) && ( v1 > 0 ) && ( v3 > 0 ) && ( s1 >= 0 ) && ( s2 >= 0 ) && ( s3 >= 0 ) ) //Критерии ввода данных.//

{

s1 *= 0.001 ; v1 *= 0.001 ; s2 *= 0.001 ; s3 *= 0.001 ; //Перевод единиц в систему СИ. (м --> км, м/час --> км/час) //

ss = s1 + s2 + s3 ; //Найдем весь путь//

t1 = s1 / v1 ; t2 = s2 / v0 ; t3 = s3 / v3 ; //Найдем время за которое второй путник преодолевает каждую часть пути//

if ( ( ss - t1 * v0 - s1 ) <= 0 ) //Условие встречи двух путников на первом промежутке пути//

{

time = ss / ( v0 + v1 ) ; //Нахождение времени встречи//

place = time * v0 ; //Нахождение места встречи//

printf("Путники встретились на расстоянии %5.3lf км от пункта В через %5.3lf часов после старта", place, time) ; //Вывод конечного результата.//

}

else

{

if ( ( ss - ( t2 + t1 ) * v0 - s1 - s2 ) <=0 ) //Условие встречи двух путников на втором промежутке пути//

{

time = ( ss - s1 - ( v0 * t1 ) ) / ( v0 + v0 ) ; //Нахождение времени встречи//

place = ( t1 + time ) * v0 ; //Нахождение места встречи//

printf("Путники встретились на расстоянии %5.3lf км от пункта В через %5.3lf часов после старта", place, time+t1) ; //Вывод конечного результата.//

}

else

{

if ( ( ss - ( t2 + t1 + t3 ) * v0 - s1 - s2 - s3 ) <= 0 ) //Условие встречи двух путников на третем промежутке пути//

{

time = ( ss - s1 - s2 - ( v0 * ( t2 + t1 ) ) ) / ( v0 + v3 ) ; //Нахождение времени встречи//

place = ( t1 + t2 + time ) * v0 ; //Нахождение места встречи//

printf("Путники встретились на расстоянии %5.3lf км от пункта A через %5.3lf часов после старта", place, time+t1+t2) ; //Вывод конечного результата.//

}

else

{

printf("Неправильно введены данные"); //Вывод оповещения о неправильном вводе данных (при несоответствии начальным критериям).

}

return 0;

}

Можно предположить, что весь путь в задаче представлен суммой [latex]ss=s_{1}+s_{2}+s_{3}[/latex]. Для начала переведем все величины в единицы СИ:

Из метров в километры:

[latex]s_{1}=s_{1}*0.001 \Leftrightarrow s_{1}=\frac{s_{1}}{1000}[/latex],

[latex]s_{2}=s_{2}*0.001 \Leftrightarrow s_{2}=\frac{s_{2}}{1000}[/latex],

[latex]s_{3}=s_{3}*0.001 \Leftrightarrow s_{3}=\frac{s_{3}}{1000}[/latex].

Из метров/час в километры/час: [latex]v_{1}=v_{1}*0.001 \Leftrightarrow v_{1}=\frac{v_{1}}{1000}[/latex]

Найдем место встречи. Тут может быть три случая:

Встреча двух путников на первом промежутке пути. Тогда время встречи можно вычислить по формуле: [latex]time = \frac{ss}{( v_{0} + v_{1} )}[/latex] , а место встречи — [latex]place = time * v_{0}[/latex]
Встреча двух путников на втором промежутке пути: Тогда время встречи можно вычислить по формуле: [latex]time =\frac{ss — s_{1} — ( v_{0} * t_{1} ) }{ v_{0} + v_{0} }[/latex] , а место встречи — [latex]place = ( t_{1} + time ) * v_{0}[/latex].
Встреча двух путников на третьем промежутке пути: Тогда время встречи можно вычислить по формуле: [latex]time = \frac{ ss — s_{1} — s_{2} — ( v_{0} * t_{2} )}{ v_{0}+ v_{3} }[/latex], а место встречи — [latex] place = ( t_{1}+t_{2} + time ) * v_{0}[/latex].

Если путники встречаются на первом промежутке пути, то их скорости суммируются (т.к. тела движутся на встречу друг к другу), при делении всего пути на сумму этих скоростей получим время встречи, расстояние можно найти умножив время встречи на скорость первого путника.

Если путники встречаются на втором промежутке пути, то их скорости аналогично суммируются, но в формуле нахождения времени встречи учитывается путь, пройденный путниками за первый промежуток времени, эту разность делим на сумму скоростей и получаем время встречи. Для того чтобы найти место встречи сложим время путников в пути и время встречи поделим на скорость и найдем место встречи.

Аналогично и на третьем промежутке пути. В формуле нахождения времени встречи учитывается путь, пройденный путниками за первый и за второй промежутки времени, эту разность делим на сумму скоростей и получаем время встречи.

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Meeting
{
    public static void main (String[] args) throws java.lang.Exception
    {
        double place, ss, time, t1, t2, t3, tt; //Описание переменных для хранения входных данных.//
        Scanner in = new Scanner(System.in);
        //Чтение из стандартного потока ввода.//
        double v0 = in.nextDouble();
        double v1 = in.nextDouble();
        double v3 = in.nextDouble();
        double s1 = in.nextDouble();
        double s2 = in.nextDouble();
        double s3 = in.nextDouble();
        if ((v0 > 0) && (v1 > 0) && (v3 > 0) && (s1 >= 0) && (s2 >= 0) && (s3 >= 0))  //Критерии ввода данных.//
        {
            s1 *= 0.001; v1 *= 0.001; s2 *= 0.001; s3 *= 0.001; //Перевод единиц в систему СИ. (м --> км, м/час --> км/час) //
            ss = s1 + s2 + s3; //Найдем весь путь//
            t1 = s1 / v1; t2 = s2 / v0; t3 = s3 / v3; //Найдем время за которое второй путник преодолевает каждую часть пути//
            if ((ss - t1 * v0 - s1) <= 0) //Условие встречи двух путников на первом промежутке пути//
            {
                time = ss / (v0 + v1);  //Нахождение времени встречи//
                place = time * v0;  //Нахождение места встречи// 
                System.out.printf("Путники встретились на расстоянии " + place + " км от пункта В через " + time + " часов после старта"); //Вывод конечного результата.//
            } 
            else
            {
                if ((ss - (t2 + t1) * v0 - s1 - s2) <= 0) //Условие встречи двух путников на втором промежутке пути//
                {
                    time = (ss - s1 - (v0 * t1)) / (v0 + v0); //Нахождение времени встречи//
                    place = (t1 + time) * v0; //Нахождение места встречи// 
                    tt = time + t1;
                    System.out.printf("Путники встретились на расстоянии " + place + " км от пункта В через " + tt + " часов после старта") ; //Вывод конечного результата.//
                }
                else 
                {
                    if ((ss - (t2 + t1 + t3) * v0 - s1 - s2 - s3) <= 0) //Условие встречи двух путников на третем промежутке пути//
                    {
                        time = (ss - s1 - s2 - (v0 * (t2 + t1))) / (v0 + v3); //Нахождение времени встречи//
                        place = (t1 + t2 + time) * v0; //Нахождение места встречи// 
                        tt = time + t1 + t2;
                        System.out.printf("Путники встретились на расстоянии " + place + " км от пункта A через " + tt + " часов после старта"); //Вывод конечного результата.//
                    }
                }
            }
        }
        else 
        {
            System.out.printf("Неправильно введены данные"); //Вывод оповещения о неправильном вводе данных (при несоответствии начальным критериям).
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Meeting

{

public static void main (String[] args) throws java.lang.Exception

{

double place, ss, time, t1, t2, t3, tt; //Описание переменных для хранения входных данных.//

Scanner in = new Scanner(System.in);

//Чтение из стандартного потока ввода.//

double v0 = in.nextDouble();

double v1 = in.nextDouble();

double v3 = in.nextDouble();

double s1 = in.nextDouble();

double s2 = in.nextDouble();

double s3 = in.nextDouble();

if ((v0 > 0) && (v1 > 0) && (v3 > 0) && (s1 >= 0) && (s2 >= 0) && (s3 >= 0)) //Критерии ввода данных.//

{

s1 *= 0.001; v1 *= 0.001; s2 *= 0.001; s3 *= 0.001; //Перевод единиц в систему СИ. (м --> км, м/час --> км/час) //

ss = s1 + s2 + s3; //Найдем весь путь//

t1 = s1 / v1; t2 = s2 / v0; t3 = s3 / v3; //Найдем время за которое второй путник преодолевает каждую часть пути//

if ((ss - t1 * v0 - s1) <= 0) //Условие встречи двух путников на первом промежутке пути//

{

time = ss / (v0 + v1); //Нахождение времени встречи//

place = time * v0; //Нахождение места встречи//

System.out.printf("Путники встретились на расстоянии " + place + " км от пункта В через " + time + " часов после старта"); //Вывод конечного результата.//

}

else

{

if ((ss - (t2 + t1) * v0 - s1 - s2) <= 0) //Условие встречи двух путников на втором промежутке пути//

{

time = (ss - s1 - (v0 * t1)) / (v0 + v0); //Нахождение времени встречи//

place = (t1 + time) * v0; //Нахождение места встречи//

tt = time + t1;

System.out.printf("Путники встретились на расстоянии " + place + " км от пункта В через " + tt + " часов после старта") ; //Вывод конечного результата.//

}

else

{

if ((ss - (t2 + t1 + t3) * v0 - s1 - s2 - s3) <= 0) //Условие встречи двух путников на третем промежутке пути//

{

time = (ss - s1 - s2 - (v0 * (t2 + t1))) / (v0 + v3); //Нахождение времени встречи//

place = (t1 + t2 + time) * v0; //Нахождение места встречи//

tt = time + t1 + t2;

System.out.printf("Путники встретились на расстоянии " + place + " км от пункта A через " + tt + " часов после старта"); //Вывод конечного результата.//

}

else

{

System.out.printf("Неправильно введены данные"); //Вывод оповещения о неправильном вводе данных (при несоответствии начальным критериям).

}