Category Archives: 2. Программы с ветвлением

Программы с простым ветвлением процесса выполнения в зависимости от некоторых условий. Ветвления в них обычно реализуются условным оператором или тернарной операцией.

Программы с ветвлением

Опубликовано: 11/10/2014

В этом разделе нам придется писать программы в которых вычислительный процесс проходит по-разному в зависимости от выполнения или нарушения некоторого условия. Условия будут иногда довольно сложные. Организовать такое ветвление мы можем либо при помощи условного выражения (тернарной операции __?__:__), либо при помощи условного оператора (if(__)…else…). Обратите внимание, что если в зависимости от некоторого условия значение … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Поврежденная картина — очень хорошая задача для тренировки, масса различных ситуаций, которые нужно учесть. Но не все предусмотрено в тестах и неправильная программа может успешно пройти проверку. Требует знания основ школьного курса геометрии.
Две окружности —
задача аналогична предыдущей, но существенно проще.
Паук и муха
Количество участников олимпиады
Новый шкаф
Сыр для Анфисы
Компакт-диски
Среднее число
Торт
Олимпиада
Номер квартиры
Прямоугольник
Скидки — НЕ используйте функции min() и max()
Точка и треугольник
Отрезок и окружности
Уровень учебных достижений
Первая или последняя?
Какой треугольник?
Квадратное уравнение
Прямоугольный или нет?
Какая четверть?
Время года
Параллелограмм
Интересная сумма
Прямоугольник

Опубликованные решения:

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:

e-olymp 7337. Discounts

12/12/2017 by Яна Колчинская

Task

In the supermarket of electronics, if you believe in TV commercials, there is a system of discounts: from two purchased goods fully paid only the cost of a higher-value product, and the other is provided free of charge. What amount of money is enough to pay for the purchase of three goods, if the price of each is known.

Input data:

Three natural numbers [latex]a, b, c[/latex] are prices of three products [latex]\left(1 ≤ a, b, с ≤ 10000\right)[/latex].

Output data:

Purchase cost.

Tests

#	Input data	Output data
1	2 2 2	4
2	78 2 45	80
3	452 89 88	540
4	50 4 67	71
5	15 37 20	52

Code

#include <iostream>
using namespace std;

int main() {
    int a, b,c, s=0; // "s" used as an auxiliary variable to store the amount of money
    cin>>a>>b>>c;
    if (a>=b && a>=c) {
        s=a;
        if (b>=c) {
            s+=c;
        }
        else s+=b;
    } 
    else if (b>=a && b>=c) {
        s=b;
        if (a>=c) {
            s+=c;
        }
        else s+=a;
    } else if (c>=a && c>=b) {
        s=c;
        if (a>=b) {
            s+=b;
        }
        else s+=a;
    }
    cout<<s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b,c, s=0; // "s" used as an auxiliary variable to store the amount of money

cin>>a>>b>>c;

if (a>=b && a>=c) {

s=a;

if (b>=c) {

s+=c;

}

else s+=b;

}

else if (b>=a && b>=c) {

s=b;

if (a>=c) {

s+=c;

}

else s+=a;

} else if (c>=a && c>=b) {

s=c;

if (a>=b) {

s+=b;

}

else s+=a;

}

cout<<s;

return 0;

}

Solution of the problem

Algorithm: you will have to pay the highest price, so let’s find it at first and save it in the variable s. Next, you need to select the product for free receipt, which you put in a couple of the most expensive. To obtain the least amount of money, the remaining goods must be the cheapest.

e-olymp 13. Паук и муха

11/12/2017 by Александра Рябова

Задача

В пустой прямоугольной комнате размерами [latex]A \times B \times C[/latex] (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке — координаты мухи [latex]X_1[/latex], [latex]Y_1[/latex] и паука [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex].

Все входные данные — целые числа, не превышающие 500.

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

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

Тесты

Входные данные	Выходные данные
$3$ $4$ $8$ $0$ $0$ $3$ $4$ $0$	$5.00$
$2$ $2$ $8$ $1$ $1$ $2$ $1$ $4$	$5.00$
$6$ $4$ $3$ $5$ $1$ $0$ $2$ $1$	$6.08$
$30$ $60$ $27$ $13$ $21$ $8$ $0$ $17$	$38.33$
$40$ $40$ $40$ $10$ $5$ $8$ $40$ $37$	$72.03$

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

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
double distance (double X1,double X2,double Y1,double Y2)
{
    return (sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)));
}
int main() {
    cout.precision(2);
    double A, B, C;
    cin>>A>>B>>C;
    double X2, Y2, X1, Y1, Z2;
    cin>>X1>>Y1;
    cin>>X2>>Y2>>Z2;
    double s=250000000;
    if (Z2==0) s=distance (X1,X2,Y1,Y2);//"floor" case
    else
    {
        if (X2==0) {X2=-Z2; s=distance (X1,X2,Y1,Y2);}//"left wall" case
        if (X2==A) {X2=A+Z2; s=distance (X1,X2,Y1,Y2);}//"right wall" case
        if (Y2==0) {Y2=-Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"near wall" case
        if (Y2==B) {Y2=B+Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"distant wall" case
    }
    cout<<fixed<<s;
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

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

{

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

}

int main() {

cout.precision(2);

double A, B, C;

cin>>A>>B>>C;

double X2, Y2, X1, Y1, Z2;

cin>>X1>>Y1;

cin>>X2>>Y2>>Z2;

double s=250000000;

if (Z2==0) s=distance (X1,X2,Y1,Y2);//"floor" case

else

{

if (X2==0) {X2=-Z2; s=distance (X1,X2,Y1,Y2);}//"left wall" case

if (X2==A) {X2=A+Z2; s=distance (X1,X2,Y1,Y2);}//"right wall" case

if (Y2==0) {Y2=-Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"near wall" case

if (Y2==B) {Y2=B+Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"distant wall" case

}

cout<<fixed<<s;

return 0;

}

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

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

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции [latex]distance[/latex].
В простейшем случае, если паук находится на полу комнаты, т.е. его координата [latex]Z_2[/latex] нулевая, координаты паука [latex]X_2[/latex] и [latex]Y_2[/latex] в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции [latex]distance[/latex].
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

Условие задачи на сайте E-Olymp
Код решения задачи

Related Images:

e-olymp 7234. Кондиціонер Степана

09/12/2017 by Александр Волынец

Задача

В офісі, де Степан працює програмістом, встановили кондиціонер нового типу. Цей кондиціонер відрізняється особливою простотою в управлінні. У кондиціонера є всього лише два керованих параметра: бажана температура і режим роботи.

Кондиціонер може працювати в наступних чотирьох режимах:

«freeze» — охолодження. У цьому режимі кондиціонер може тільки зменшувати температуру. Якщо температура в кімнаті і так не більше бажаної, то він вимикається.

«heat» — нагрів. У цьому режимі кондиціонер може тільки збільшувати температуру. Якщо температура в кімнаті і так не менше бажаної, то він вимикається.

«auto» — автоматичний режим. У цьому режимі кондиціонер може як збільшувати, так і зменшувати температуру в кімнаті до бажаної.

«fan» — вентиляція. У цьому режимі кондиціонер здійснює тільки вентиляцію повітря і не змінює температуру в кімнаті.

Кондиціонер досить потужний, тому при налаштуванні на правильний режим роботи він за годину доводить температуру в кімнаті до бажаної.

Потрібно написати програму, яка по заданій температурі в кімнаті [latex]t_{room}[/latex], встановленим на кондиціонері бажаної температурі [latex]t_{cond}[/latex] і режиму роботи визначає температуру, яка встановиться в кімнаті через годину.

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

Перший рядок вхідного файлу містить два цілих числа [latex]t_{room}[/latex], і [latex]t_{cond}[/latex], розділених рівно одним пропуском [latex](-50 ≤ t_{room}. ≤ 50 [/latex],[latex]-50 ≤ t_{cond}. ≤ 50)[/latex]. Другий рядок містить одне слово, записане малими літерами латинського алфавіту — режим роботи кондиціонера.

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

Вихідний файл повинен містити одне ціле число — температуру, яка встановиться в кімнаті через годину.

Тесты

Входные данные	Выходные данные
10 20 heat	20
10 20 freeze	10
20 10 auto	10
20 20 freeze	20

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

#include <iostream>
using namespace std;

int main()
{
    int tr, tc;
    string cond;
    cin >> tr >> tc >> cond;
    if ((tr >= tc && cond == "freeze") || (tr <= tc && cond == "heat") || cond == "auto")
        cout << tc;
    else cout << tr;
}

#include <iostream>

using namespace std;

int main()

{

int tr, tc;

string cond;

cin >> tr >> tc >> cond;

if ((tr >= tc && cond == "freeze") || (tr <= tc && cond == "heat") || cond == "auto")

cout << tc;

else cout << tr;

}

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

Для решения этой задачи я построил таблицу, в которой рассмотрел все возможные варианты.

Режим работы	[latex]tr>tc[/latex]	[latex]tr>tc[/latex]	[latex]tr=tc[/latex]
freeze	tc	tr	tc
heat	tr	tc	tc
fan	tr	tr	tr
auto	tc	tc	tc

Из этой таблицы видно, что повторяется tc 7 раз, а tr — 5 раз. Поэтому опишем в операторе if все условия при которых температура в комнате будет равняться желаемой температуре через час, а во всех остальных случаях температура не изменится.

Ссылки

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 918. Какая четверть?

04/12/2017 by Георгий Мартынюк

Задача

Задана точка с координатами [latex]x[/latex] и [latex]y[/latex]. Определить, в какой координатной четверти она расположена.

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

В единственной строке через пробел заданы [latex]2[/latex] вещественных числа — координаты точки, значения координат по модулю не превышают [latex]100[/latex].

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

Единственное число — номер соответствующей четверти, либо [latex]0[/latex] , если однозначно определить четверть невозможно.

Тесты

Входные данные		Выходные данные
[latex]x[/latex]	[latex]y[/latex]	Четверть
12	31	1
-10	18	2
-15	-25	3
13	-13	4
0	0	0

#include <iostream> 
#include <cmath>
using namespace std;
int main() {
    float x, y;
    cin >> x >> y;
    if (x > 0 && y > 0) {
            cout << "1" << endl;
    }
    else if (x < 0 && y > 0) {
            cout << "2" << endl;
    }
    else if (x < 0 && y < 0) {
            cout << "3" << endl;
    }
    else if (x > 0 && y < 0) {
            cout << "4" << endl;
    }
    else {
            cout << "0" << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

float x, y;

cin >> x >> y;

if (x > 0 && y > 0) {

cout << "1" << endl;

}

else if (x < 0 && y > 0) {

cout << "2" << endl;

}

else if (x < 0 && y < 0) {

cout << "3" << endl;

}

else if (x > 0 && y < 0) {

cout << "4" << endl;

}

else {

cout << "0" << endl;

}

return 0;

}

Решение

Четверти координатной плоскости

В прямоугольной системе координат на плоскости выделяют 4 четверти: 1, 2, 3, 4.
1-й четветри соответствуют точки, имеющие обе ([latex]x[/latex] и [latex]y[/latex]) положительные координаты.
2-ая четверть: [latex]x \lt 0[/latex], [latex]y \gt 0[/latex].
3-ая четверть: [latex]x \lt 0[/latex], [latex]y \lt 0[/latex].
4-ая четверть: [latex]x \gt 0[/latex], [latex]y \lt 0[/latex].
Точка с координатами ([latex]0[/latex];[latex]0[/latex]), находится в начале координат.
Если точка лежит на оси [latex]«Oy»[/latex], то её абсцисса равна [latex]0[/latex].
Если точка лежит на оси [latex]«Ox»[/latex], то её ордината равна [latex]0[/latex].

Ссылки

e-olymp
Ideone

Related Images:

e-olymp 130. Прямоугольник

04/12/2017 by Костя Григорян

Задача №130 (дубль — №7379)

Заданы координаты трёх вершин прямоугольника. Найдите координаты четвертой вершины.

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

В единственной строке записано шесть чисел — координаты трёх точек.

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

Два числа, координаты искомой вершины прямоугольника. Все входные и выходные данные — целые числа, не превышающие по модулю [latex]100[/latex].

Тесты

Входные данные	Выходные данные
[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]1[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]2[/latex] [latex]0[/latex]
[latex]1\, 4\, 4\, 0\, 0\, 2[/latex]	[latex]5\, 2[/latex]
[latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]-100[/latex]	[latex]-100[/latex] [latex]100[/latex]
[latex]2[/latex] [latex]-1[/latex] [latex]3[/latex] [latex]1[/latex] [latex]-2[/latex] [latex]1[/latex]	[latex]-1[/latex] [latex]3[/latex]
[latex]8\, 0\, 1\, 6\, 0\, 4[/latex]	[latex]9\, 2[/latex]

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

#include <iostream>
using namespace std;

int main() {
    int x1, x2, x3, y1, y2, y3;
    cin  >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0)
    {
        cout << x2+x3-x1 << " " << y2+y3-y1;
    }
    else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0)
    {
        cout << x1+x3-x2 << " " << y1+y3-y2;
    }
    else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0)
    {
        cout << x1+x2-x3 << " " << y1+y2-y3;
    }   
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x1, x2, x3, y1, y2, y3;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0)

{

cout << x2+x3-x1 << " " << y2+y3-y1;

}

else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0)

{

cout << x1+x3-x2 << " " << y1+y3-y2;

}

else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0)

{

cout << x1+x2-x3 << " " << y1+y2-y3;

}

return 0;

}

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

Прямоугольник

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [latex]x_4=x_1+x_3-x_2[/latex] и [latex]y_4=y_1+y_3-y_2[/latex]. Но мы не знаем какая из входных вершин противоположна четвертой, а какие — прилежащие. Так как наша фигура это прямоугольник, то противоположная вершина будет при угле [latex]90^{\circ}[/latex]. Произведение перпендикулярных векторов дает [latex]0[/latex]. Перебрав три варианта произведения векторов, заданных входными вершинами, находим вершину при угле [latex]90^{\circ}[/latex]. Остальные две, соответственно, будут прилежащими. Находим координаты четвертой вершины по формуле, заданной выше.

Ссылки

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

Related Images:

e-olymp 7107. Без лифта

02/12/2017 by Кирилл Волков

Задача

Три друга – Андрей, Борис и Владимир живут соответственно на $a$, $b$ и $v$ этажах многоэтажного дома. Они занимаются спортом, поэтому никогда не пользуются лифтом. Однажды им потребовалось срочно встретиться у кого-то из них дома.

Составьте программу, которая определяла бы номер этажа, на котором они встретятся, при чем время до встречи было бы минимальным. Учтите, что скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема.

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

Программа получает на вход три натуральных числа – номера этажей, на которых живут друзья ($1 \leq a, b, v \leq 28$).

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

Программа выводит номер этажа, на котором они встречаются.

Тесты

Входные данные	Выходные данные
$1$ $5$ $8$	$5$
$1$ $1$ $2$	$1$
$4$ $11$ $14$	$4$
$6$ $3$ $2$	$3$
$2$ $9$ $1$	$2$

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int minFloor = min(min(a, b), c);
    int maxFloor = max(max(a, b), c);
    int middleFloor = a + b + c - minFloor - maxFloor;
    int resultFloor;
    if(31 * (maxFloor - minFloor) < 47 * (middleFloor - minFloor)){
        resultFloor = minFloor;
    }
    else{
        resultFloor = middleFloor;
    }
    cout << resultFloor;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

int minFloor = min(min(a, b), c);

int maxFloor = max(max(a, b), c);

int middleFloor = a + b + c - minFloor - maxFloor;

int resultFloor;

if(31 * (maxFloor - minFloor) < 47 * (middleFloor - minFloor)){

resultFloor = minFloor;

}

else{

resultFloor = middleFloor;

}

cout << resultFloor;

return 0;

}

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

По условию скорость спуска по лестнице в $\frac{47}{31}$ раза больше, чем скорость подъема. Назовем эту величину коэффициентом подъема.
Примем, что человек спускается на один этаж за единицу времени. Тогда он поднимается на один этаж за единицу времени, умноженную на коэффициент подъема.
Вначале необходимо установить, какой из этажей является максимальным, какой — минимальным, какой — промежуточным.
Очевидно, что друг, живущий на промежуточном этаже доберется до максимального этажа быстрее, чем тот, кто живет на минимальном, а также доберется до минимального этажа быстрее, чем тот, кто живет на максимальном. Кроме того, друг, живущий на максимальном этаже, быстрее спустится на минимальный этаж, чем живущий на минимальном поднимется на максимальный. Отсюда получаем, что если друзья будут подниматься на максимальный этаж, то потраченное время не будет наименьшим возможным. То есть друзья могут встретиться либо на минимальном, либо на промежуточном этаже. Время, потраченное на спуск на минимальный этаж, численно равно разнице между максимальным и минимальным этажом. Время, потраченное на путь к промежуточному этажу, численно равно максимуму между разницей между минимальным и промежуточным этажами, умноженной на коэффициент подъема и разницей между максимальным и промежуточным этажами. Так как разница между максимальным и промежуточным этажами всегда не превышает разницы между максимальным и минимальным этажами, то для определения искомого этажа нам достаточно сравнивать разницу между максимальным и минимальным этажами и разницу между минимальным и промежуточным этажами, умноженной на коэффициент подъема.
В случае, если первая величина будет меньше второй, то друзья должны встретиться на минимальном этаже, в противном случае — на промежуточном.

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

Ссылки

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

Related Images:

e-olymp 43. Количество участников олимпиады

01/12/2017 by Мороз Дима

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью. В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d \left(1 ≤ k, n, m, d ≤ 1000 \right)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$	$n$	$m$	$d$	Выходные данные
2	4	7	3	28
4	5	2	1	20
3	7	5	4	-1
6	6	6	1	-1
2	3	6	4	-1
3	2	5	8	-1

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){
    float k, n, m, d, s;
    cin >> k >> n >> m >> d;
    s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);
    if((1/k + 1/n + 1/m >= 1) || (floor(s/k) != s/k || floor(s/n) != s/n || floor(s/m) != s/m) || !(floor(s) == s)){
    cout << "-1";
    }else{
        cout << s;
    }
    
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

float k, n, m, d, s;

cin >> k >> n >> m >> d;

s = (d * k * n * m) / (k * n * m - k * m - k * n - m * n);

if((1/k + 1/n + 1/m >= 1) || (floor(s/k) != s/k || floor(s/n) != s/n || floor(s/m) != s/m) || !(floor(s) == s)){

cout << "-1";

}else{

cout << s;

}

return 0;

}

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

Пусть $x$ — количество учеников Пифагора. Тогда $\frac{x} {2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\frac{x} {4}$ — ученики, которые изучают природу, а $\frac{x} {7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.
Получили уравнение вида $\frac{x} {2} + \frac{x} {4} + \frac{x} {7} + 3 = x$, в общем виде $\frac{x} {k} + \frac{x} {m} + \frac{x} {n} + d = x$.
Отсюда выходит, что $\frac{1} {k} + \frac{1} {m} + \frac{1} {n} + \frac{d} {x} = 1;$
$\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$
$(mn + kn + km)x + kmnd = kmnx;$
Отсюда получаем формулу $x = \frac{kmnd} {kmn — mn — kn — km}$.
Следовательно, если мы получаем целое число, то секретарь оказался прав, а если число дробное, то секретарь ошибся.

Для того, чтобы проверить, является ли переменная $x$ целым числом или нет, используем функцию floor() из встроенной библиотеки <cmath>.

Помимо этого делаем проверку для суммы чисел $\frac{1} {k}$, $\frac{1} {n}$ и $\frac{1} {m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\frac{q} {k}$, $\frac{q} {n}$ и $\frac{q} {m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Related Images:

e-olymp 112. Торт

26/11/2017 by Илья Черноморец

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

Сколько времени потребуется толстякам, чтобы съесть весь праздничный торт вместе?

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

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $10000$.

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

Вывести время в часах, за которое толстяки вместе могут съесть торт. Результат округлить до двух десятичных знаков.

TESTS

$t_1$	$t_2$	$t_3$	$t$
3	3	3	1.00
4	67	50	3.51
228.22	8	2.28	1.76
1577	157.7	15.77	14.21

C ветвлением:

#include<iostream>
#include<iomanip>

using namespace std;
int main(){
    double t1,t2,t3;
    cin >> t1 >> t2 >> t3;
    double t;
    t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);
    if(t1*t2*t3 == 0) cout<<0;
        else cout<<fixed<<setprecision(2)<<t;
    return 0;
}

#include<iostream>

#include<iomanip>

using namespace std;

int main(){

double t1,t2,t3;

cin >> t1 >> t2 >> t3;

double t;

t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);

if(t1*t2*t3 == 0) cout<<0;

else cout<<fixed<<setprecision(2)<<t;

return 0;

}

Без ветвления:

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

int main() {
    double t1, t2, t3;
    cin >> t1 >> t2 >> t3;
    double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;
    cout << setprecision(2) << fixed << t;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

double t1, t2, t3;

cin >> t1 >> t2 >> t3;

double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;

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

return 0;

}

Решение с ветвлением

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t_1}-\frac{t}{t_2}-\frac{t}{t_3}=0;$
$\frac{t}{t_1}+\frac{t}{t_2}+\frac{t}{t_3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t\left(t_1t_2+t_2t_3+t_1t_3\right)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Решение без ветвления

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $\left(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}\right)$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков. Для этого воспользуемся функцией setprecision() и её аргументом fixed

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

1	cout << setprecision(2) << fixed << t;

Ссылки

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

Related Images:

Ю 2.27. Шашечный эндшпиль

19/05/2017 by Валентина Андриеш

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Условие задачи:
В шашечном эндшпиле остались белая дамка и две черных пешки, позиции которых известны. Ход белых. Сможет ли дамка срубить одну или сразу обе пешки?
Continue reading →

Related Images:

КМ259(б). Квартеты из клеток

17/11/2016 by Антон Куперман

Задача

Назовем квартетом четверку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. Какое наибольшее число квартетов, не имеющих общих клеток, можно разместить в прямоугольнике [latex]m\times n[/latex] клеток?

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

[latex]m[/latex],[latex]n[/latex]

Вывод

[latex]x[/latex]-кол-во квартетов.

Тесты

m	n	x
8	6	12
16	7	24
17	8	29,75
15	11	37

Код

#include <iostream>
using namespace std;

int main() {
    int m, n;
    double x;
    cin >> m >> n;
    if(m%2==0 && n%2==0)
    {
        x=(m*n)/4;
    } else if(m%2==0 && n%2!=0) 
    {
        x=(m*(n-1))/4;
    } else if(m%2!=0 && n%2==0)
    {
        x=(m*(n-1))/4;
    } else 
    {
        x=(m*(n-1)-2)/4;
    }
    cout << x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n;

double x;

cin >> m >> n;

if(m%2==0 && n%2==0)

{

x=(m*n)/4;

} else if(m%2==0 && n%2!=0)

{

x=(m*(n-1))/4;

} else if(m%2!=0 && n%2==0)

{

x=(m*(n-1))/4;

} else

{

x=(m*(n-1)-2)/4;

}

cout << x;

return 0;

}

Решение

Если [latex]m[/latex] и [latex]n[/latex] четные, то в прямоугольнике [latex]m\times n[/latex] можно разместить [latex]m/n[latex] квартетов. Если [latex]m[/latex] четное, а [latex]n[/latex] нечетное (и наоборот), то квартетов — [latex]m(n-1)/4[/latex]. И наконец если [latex]m[/latex] и [latex]n[/latex] — нечетные, то формула будет выглядеть так: [latex]m(n-1)-2/4[/latex].

Related Images:

КМ.72

13/11/2016 by Лена Бригарь

Задача из журнала «Квант» №72

Условие:
Пусть p — произвольное вещественное число. Найдите все такие x, что сумма кубических корней из чисел 1 – x и 1 + x равна p.

Тесты:

№	Входные данные	Выходные данные
1	0.6	No solutions
2	1.4	x1 = -0.997217 x2 = 0.997217
3	2	x=0
4	1.79	x1 = -0.814516 x2 = 0.814516

Код

#include 
#include 
#define _USE_MATH_DEFINES
using namespace std;
int main() {
    double p;
    cin >> p;
    if(p < pow(2, (double)1/3) || p > 2) { // Если корней нет
        cout << "No solutions";
    } 
    else { // Корни есть
        if(p == 2) { // Если корень один
            cout << "x = 0";
        } 
        else { // Корней два
            double x1 = -sqrt(-pow(p, 9) + 6 * pow(p, 6) + 15 * pow(p, 3) + 8) / pow(3 * p, 1.5);
            double x2 = sqrt(-pow(p, 9) + 6 * pow(p, 6) + 15 * pow(p, 3) + 8) / pow(3 * p, 1.5);
            cout << "x1 = " << x1 << endl;
            cout << "x2 = " << x2;
        }
    }
return 0;
}

#include

#define _USE_MATH_DEFINES

using namespace std;

int main() {

double p;

cin >> p;

if(p < pow(2, (double)1/3) || p > 2) { // Если корней нет

cout << "No solutions";

}

else { // Корни есть

if(p == 2) { // Если корень один

cout << "x = 0";

}

else { // Корней два

double x1 = -sqrt(-pow(p, 9) + 6 * pow(p, 6) + 15 * pow(p, 3) + 8) / pow(3 * p, 1.5);

double x2 = sqrt(-pow(p, 9) + 6 * pow(p, 6) + 15 * pow(p, 3) + 8) / pow(3 * p, 1.5);

cout << "x1 = " << x1 << endl;

cout << "x2 = " << x2;

}

return 0;

}

Решение:
Рассмотрев условие, приходим к такому уравнению [latex] \sqrt[3]{\left(1+x \right)}+\sqrt[3]{\left(1-x \right)}=p [/latex] , где p — параметр, который будет задаваться на входе.Ответы для р будут существовать на промежутке [latex] \left[\sqrt[3]{2}; 2\right] [/latex] . Если р не входит в промежуток, то выводим «нет решений». Если р=2, то оба корня совпадут, по этому выводим один «х=0». Для остальных случаев ответом будет два корня.

Ссылки:
Решение на ideone http://ideone.com/A8DXC9
Условие http://www.kvant.info/zkm_1971.htm
Решение wolfram http://www.wolframalpha.com/input/?i=(1%2Bx)%5E(1%2F3)+%2B+(1-x)%5E(1%2F3)+%3D+p

Related Images:

Mif 9. Пересечение отрезков

06/11/2016 by Андреев Даниил

Задача

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин на плоскости, определить имеют ли они общие точки.

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

Координаты концов отрезка[latex]AB[/latex] и [latex]CD[/latex].

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

Пересекаются ли отрезки.

Тесты

Входные данные								Выходные данные
[latex]x1[/latex]	[latex]y1[/latex]	[latex]x2[/latex]	[latex]y2[/latex]	[latex]x3[/latex]	[latex]y3[/latex]	[latex]x4[/latex]	[latex]y4[/latex]
1	0	2	1	1	0	2	0	Отрезки пересекаются
-1	1	2	-2	0	-2	1	3	Отрезки пересекаются
1	1	2	2	2	2	1	1	Отрезки пересекаются
-1	1	-1	2	1	1	2	2	Отрезки не пересекаются
-2	-1	-2	3	0	-1	0	3	Отрезки не пересекаются
-2	0	0	2	0	-2	1	1	Отрезки не пересекаются

Код программы на C++

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    double x1, y1, x2, y2, x3, y3, x4, y4;
    double Ua, Ub, numerator_a, numerator_b, denominator;
    
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);
    if (denominator == 0){
        if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)
            cout << "Отрезки пересекаются";
        else cout << "Отрезки не пересекаются";
    }
    else{
        numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);
        numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);
        Ua=numerator_a/denominator;
        Ub=numerator_b/denominator;
        cout << (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1 ? "Отрезки пересекаются" : "Отрезки не пересекаются");
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double x1, y1, x2, y2, x3, y3, x4, y4;

double Ua, Ub, numerator_a, numerator_b, denominator;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);

if (denominator == 0){

if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)

cout << "Отрезки пересекаются";

else cout << "Отрезки не пересекаются";

}

else{

numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);

numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);

Ua=numerator_a/denominator;

Ub=numerator_b/denominator;

cout << (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1 ? "Отрезки пересекаются" : "Отрезки не пересекаются");

}

return 0;

}

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

import java.util.*;
 
class Main{
    public static void main (String[] args) throws java.lang.Exception{
        Scanner scan = new Scanner(System.in);
        double Ua, Ub, numerator_a, numerator_b, denominator;
        double x1 = scan.nextDouble();
        double y1 = scan.nextDouble();
        double x2 = scan.nextDouble();
        double y2 = scan.nextDouble();
        double x3 = scan.nextDouble();
        double y3 = scan.nextDouble();
        double x4 = scan.nextDouble();
        double y4 = scan.nextDouble();
 
        denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);
        if (denominator == 0){
            if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0)  System.out.print("Отрезки пересекаются");
            else System.out.print("Отрезки не пересекаются");
        }
        else{
            numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);
            numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);
            Ua=numerator_a/denominator;
            Ub=numerator_b/denominator;
            if (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1)   System.out.print("Отрезки пересекаются");
            else    System.out.print("Отрезки не пересекаются");
        }
    }
}

import java.util.*;

class Main{

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

Scanner scan = new Scanner(System.in);

double Ua, Ub, numerator_a, numerator_b, denominator;

double x1 = scan.nextDouble();

double y1 = scan.nextDouble();

double x2 = scan.nextDouble();

double y2 = scan.nextDouble();

double x3 = scan.nextDouble();

double y3 = scan.nextDouble();

double x4 = scan.nextDouble();

double y4 = scan.nextDouble();

denominator=(y4-y3)*(x1-x2)-(x4-x3)*(y1-y2);

if (denominator == 0){

if ( (x1*y2-x2*y1)*(x4-x3) - (x3*y4-x4*y3)*(x2-x1) == 0 && (x1*y2-x2*y1)*(y4-y3) - (x3*y4-x4*y3)*(y2-y1) == 0) System.out.print("Отрезки пересекаются");

else System.out.print("Отрезки не пересекаются");

}

else{

numerator_a=(x4-x2)*(y4-y3)-(x4-x3)*(y4-y2);

numerator_b=(x1-x2)*(y4-y2)-(x4-x2)*(y1-y2);

Ua=numerator_a/denominator;

Ub=numerator_b/denominator;

if (Ua >=0 && Ua <=1 && Ub >=0 && Ub <=1) System.out.print("Отрезки пересекаются");

else System.out.print("Отрезки не пересекаются");

}

Решение

Пусть концы отрезков имеют координаты [latex]A(x_1,y_1)[/latex], [latex]B(x_2,y_2)[/latex], [latex]C(x_3,y_3)[/latex] и [latex]D(x_4,y_4)[/latex]. По имеющимся точкам выведем параметрические уравнения обоих отрезков: [latex]0\leq u \leq 1:[/latex] $$\begin{cases}x=u x_1+(1−u)x_2; \newline y=uy_1+(1−u)y_2\end{cases};$$ и [latex] 0\leq v \leq 1:[/latex] $$\begin{cases}x=vx_3+(1−v)x_4 \newline y=vy_3+(1−v)y_4\end{cases}$$
В точке пересечения [latex]x[/latex] и [latex]y[/latex] должны совпадать. Значит выходит система двух линейных уравнений, которую нужно решить относительно [latex]u[/latex] и [latex]v:[/latex] $$\begin{cases}ux_1+(1−u)x_2=vx_3+(1−v)x_4 \newline uy_1+(1−u)y_2=vy_3+(1−v)y4\end{cases}$$
Найдем определитель: [latex]denominator=(y_4-y_3)\cdot(x_1-x_2)-(x_4-x_3)\cdot(y_1-y_2).[/latex] Если он равен [latex]0[/latex], то прямые содержащие отрезки параллельны или совпадают. В этом случае проверим лежит ли вершина одного отрезка на другом, если она лежит, то отрезки пересекаются, иначе не пересекаются.
Если не [latex]0[/latex], то найдем решение по правилу Крамера:
$$\begin{cases}Ua=\frac{(x_4-x_2)\cdot(y_4-y_3)-(x_4-x_3)\cdot(y_4-y_2)}{denominator} \newline Ub=\frac{(x_1−x_2)\cdot(y_4−y_2)−(x_4−x_2)\cdot(y_1−y_2)}{denominator}\end{cases}$$
Если [latex]0\leq Ua \leq 1[/latex] и [latex]0\leq Ub \leq 1[/latex], то отрезки пресекаются, иначе отрезки не пересекаются.

Ссылки

Ideone C++
Ideone Java

Related Images:

A60г

31/10/2016 by Алла Марокко

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть u определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом: [latex] u=\begin{cases}x^{2}-1, ; \text{ if } (x, y)\in D \\sqrt{\left| x-1 \right| } ; \text{ another case }\end{cases}[/latex] (запись [latex] (x, y)\in D [/latex] означает, что точка с координатами [latex]x, y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y.[/latex] Определить [latex]u.[/latex]

Тесты:

№	Вход		Выход
	[latex]x[/latex]	[latex]y[/latex]	[latex]u[/latex]
1	0.3	0.3	0.836660
2	1	1	0.000000
3	2	2	1.000000
4	0	0	-1.000000

Код на языке C++:

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

int main() {
    float x, y, u;
    scanf("%f%f", &x, &y);
    float a=x*x+y*y;
    if((y<0)||(a>1)||((x>0)&&(a<0.3)))
    {
        printf("u=%f", sqrt(abs(x-1)));
    }
    else
    {
        printf("u=%f",x*x-1);
    }

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

float x, y, u;

scanf("%f%f", &x, &y);

float a=x*x+y*y;

if((y<0)||(a>1)||((x>0)&&(a<0.3)))

{

printf("u=%f", sqrt(abs(x-1)));

}

else

{

printf("u=%f",x*x-1);

}

return 0;

}

Код на языке Java:

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


class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        float x = in.nextFloat();
        float y = in.nextFloat();
        float a=x*x+y*y;
        if((y<0)||(a>1)||((x>0)&&(a<0.3))){
            System.out.println(Math.sqrt(Math.abs(x-1)));
        }
        else{
            System.out.println(x*x-1);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

float x = in.nextFloat();

float y = in.nextFloat();

float a=x*x+y*y;

if((y<0)||(a>1)||((x>0)&&(a<0.3))){

System.out.println(Math.sqrt(Math.abs(x-1)));

}

else{

System.out.println(x*x-1);

}

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex] y<0 [/latex].Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3 .
Ссылки:
Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .

Related Images:

KM2. Радиус окружностей, удовлетворяющих условию

19/10/2016 by Вадим Гордийчук

Задача

Дана сфера радиуса [latex]1[/latex]. На ней расположены равные окружности [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex] радиуса [latex]r \left(n \ge 3\right)[/latex]. Окружность [latex]\gamma_0[/latex] касается всех окружностей [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex]; кроме того, касаются друг друга окружности [latex]\gamma_1[/latex] и [latex]\gamma_2[/latex]; [latex]\gamma_2[/latex] и [latex]\gamma_3[/latex]; [latex]\ldots[/latex]; [latex]\gamma_n[/latex] и [latex]\gamma_1[/latex].
При каких [latex]n[/latex] это возможно? Вычислить соответствующий радиус [latex]r[/latex].

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

Количество окружностей [latex]n[/latex].

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

Радиус окружностей [latex]r[/latex].

Тесты

Входные данные ([latex]n[/latex])	Выходные данные ([latex]r[/latex])
3	0.816497
4	0.707107
5	0.525731
6	Solution does not exist.

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

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

int main() {
    unsigned int n; double s_2, r;
    cin >> n;
    if ((n < 3) || (n > 5)) cout << "Solution does not exist." << endl;
    else
    {
        s_2 = sin(M_PI/n);
        s_2 *= s_2; //Возведение синуса во вторую степень.
        r = sqrt(1 - 1/(4.0*s_2));
        cout << r << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

unsigned int n; double s_2, r;

cin >> n;

if ((n < 3) || (n > 5)) cout << "Solution does not exist." << endl;

else

{

s_2 = sin(M_PI/n);

s_2 *= s_2; //Возведение синуса во вторую степень.

r = sqrt(1 - 1/(4.0*s_2));

cout << r << endl;

}

return 0;

}

import java.util.*;

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        if ((n < 3) || (n > 5)) System.out.println("Solution does not exist.");
        else
        {
            double s_2 = Math.sin(Math.PI / n);
            s_2 *= s_2;
            double r = Math.sqrt(1-1/(4.0*s_2));
            System.out.println(r);
        }
    }
}

import java.util.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

if ((n < 3) || (n > 5)) System.out.println("Solution does not exist.");

else

{

double s_2 = Math.sin(Math.PI / n);

s_2 *= s_2;

double r = Math.sqrt(1-1/(4.0*s_2));

System.out.println(r);

}

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

Каждой окружности на сфере можно сопоставить её «центр на сфере» — конец радиуса сферы, проходящего через центр окружности (никогда не лежащий на сфере). Эту точку мы будем называть «центром» окружности в кавычках, подчёркивающих, что это не «обычный» центр (рис. 2, а).

Заметим для точности, что такого определённого «центра» нет у окружностей больших кругов сферы. Но окружности, о которых идёт речь в условии задачи, заведомо не могут иметь радиус [latex]1[/latex], потому что окружности двух больших кругов не могут друг друга касаться, — они всегда пересекают друг друга в двух диаметрально противоположных точках сферы.

Точка касания двух окружностей, расположенных на сфере (см. рис. 2, б), лежит в плоскости [latex]P[/latex], проходящей через центры окружностей и центр сферы. Действительно, обе окружности симметричны относительно плоскости [latex]P[/latex], и если бы они имели общую точку по одну сторону плоскости [latex]P[/latex], то должны были бы иметь и симметричную ей общую точку по другую сторону [latex]P[/latex], а у них всего одна общая точка. Если эти окружности имеют один и тот же радиус [latex]r[/latex], то расстояние между их «центрами» равно [latex]2r[/latex], потому что на окружности большого круга, получающейся в пересечении сферы и плоскости [latex]P[/latex] (рис. 2, в), диаметры наших окружностей (чёрные отрезки) и отрезок, соединяющий их «центры» (красный), стягивают равные дуги.

Пусть [latex]A_0[/latex], [latex]A_1[/latex], [latex]A_2[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] — «центры» окружностей [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex], о которых идёт речь в условии задачи. Тогда [latex]A_0 A_1=A_0 A_2=\ldots=A_0 A_n=A_1 A_2=A_2 A_3=\ldots=A_n A_1=2r[/latex], другими словами, [latex]A_0 A_1 A_2 \ldots A_n[/latex] — правильная [latex]n[/latex]-угольная пирамида с вершиной [latex]A_0[/latex], у которой все боковые грани — равносторонние треугольники со сторонами равными [latex]2r[/latex]. Итак, достаточно построить пирамиду, для которой выполнены эти условия, тогда точки [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] будут определять окружности радиуса [latex]r[/latex], с «центрами» [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex], которые, очевидно, удовлетворяют условию задачи.

Поскольку сумма плоских углов выпуклого [latex]n[/latex]-гранного угла с вершиной [latex]A_0[/latex] меньше [latex]360^\circ[/latex]:
[latex]n\cdot60^\circ=[/latex]∠[latex]A_1 A_0 A_2+[/latex]∠[latex]A_2 A_0 A_3+\ldots+[/latex]∠[latex]A_n A_0 A_1<360^\circ[/latex], то [latex]n<6[/latex]. Для [latex]n=3[/latex], [latex]4[/latex] и [latex]5[/latex] нетрудно построить нужные пирамиды.

Пусть [latex]O[/latex] — центр сферы. Высота пирамиды [latex]h[/latex] и длина её рёбер [latex]2r[/latex] находятся из следующих соображений: радиус [latex]K A_1[/latex] основания пирамиды — катет [latex]\bigtriangleup A_0 K A_1[/latex] и боковая сторона [latex]\bigtriangleup A_1 K A_2[/latex], где ∠[latex]A_1 K A_2=2 \pi / n[/latex] (рис. 3, а , б),
[latex]\sqrt{4 r^2-h^2 \sin \frac{\pi}{n}}=r[/latex]

Из [latex]\bigtriangleup A_0 O A_1[/latex] имеем [latex]r=\frac{h}{2r}[/latex].

Отсюда [latex]h=2 r^2[/latex], [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex]

Таким образом,
при [latex]n=3[/latex]: [latex]r=\sqrt{\frac{2}{3}}[/latex] [latex]\left( \sin \frac{\pi}{3}=\frac{\sqrt{3}}{2} \right)[/latex]
при [latex]n=4[/latex]: [latex]r=\sqrt{\frac{1}{2}}[/latex] [latex]\left( \sin \frac{\pi}{4}=\frac{\sqrt{2}}{2} \right)[/latex]
при [latex]n=5[/latex]: [latex]r=\sqrt{\frac{1-\sqrt{5}}{2}}[/latex]
(формулу [latex]\sin \frac{\pi}{5}=\frac{\sqrt{10-2 \sqrt{5}}}{4}[/latex] можно вывести из рисунка 4, с помощью которого строятся правильный десятиугольник и правильный пятиугольник).

Рисунки, использованные в решении

Рисунок 2:

Рисунок 3:

Рисунок 4:

Научно-популярный журнал «Квант», 1970 год, №7, страницы 51-53

Итоги:
Выведенная во время решения формула [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex] справедлива только при [latex]n=3[/latex], [latex]4[/latex], [latex]5[/latex]. В случае, если задать значения больше этих, то выражение под корнем примет отрицательное значение, а в рамках данной задачи это будет говорить об отсутствии решения. Значения же меньше будут недопустимы, что было указано в условии.
Таким образом, программа выведет сообщение об отсутствии решения, если заданные значения [latex]n[/latex] отличны от вышеупомянутых. Если же условия будут соблюдаться, то задача выведет соответствующее значение радиуса.

Ссылки

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:

KM63

06/10/2016 by Курьянов Павел

Задача М63 из журнала «Квант» №1 за 1971 год, стр.39. Автор А.А. Кириллов.
Можно ли из плиток размером 1х2 сложить четырехугольник размером [latex] M\times N [/latex] так, чтоб при этом не было ни одного прямого «шва», соединяющего стороны квадрата и идущие по краям плиток.

Изображение как на рисунке не годиться так как тут есть «шов» [latex] AB [/latex].

Входные данные
Размеры четырёхугольника [latex] M [/latex] и [latex] N [/latex].

Выходные данные
Возможно ли это сделать [latex] Yes [/latex] или не возможно [latex] No [/latex].

Тесты

вводимые данные		выводимые данные
M	N	возможно \|\| не возможно
2	16	no
6	6	no
66	69	yes
16	5	yes
99	71	no
7	7	no
78	77	yes
7	8	yes

Код задачи

#include <iostream>
using namespace std;

int main() {
    long long m,n;
    cin>>m>>n;
    if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {  
        if (m==6 && n==6) {
            cout<<"No";// согласно решению задачи
            return 0;
        }
        cout<<"Yes";//согласно общему решению
    }
    else{ 
        cout<<"No";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long m,n;

cin>>m>>n;

if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {

if (m==6 && n==6) {

cout<<"No";// согласно решению задачи

return 0;

}

cout<<"Yes";//согласно общему решению

}

else{

cout<<"No";

}

return 0;

}

Решение
Легко доказать, что прямоугольники [latex] {2\times m}, [/latex] [latex] {3\times m}, [/latex] [latex] {4\times m} [/latex] разрезать таким образом нельзя. Если же [latex] {m\geq{5}}, [/latex] [latex] {n\geq{5}} [/latex] и [latex] mn [/latex] четно (последнее условие разумеется необходимо), то во всех случаях кроме [latex]{6\times 6}[/latex] нужное разбиение существует.
Ссылки
ideone

Related Images:

KM11. 44 дерева по чижу на каждом

05/10/2016 by Иванна Ялымова

Задача
Задача из журнала «Квант» №11-1970г.

На 44 деревьях, расположенных по окружности, сидели 44 веселых чижа (на каждом дереве по чижу). Время от времени два чижа одновременно перелетают на соседние деревья в противоположных направлениях (один – по часовой стрелке, второй – против). Докажите, что чижи никогда не соберутся на одном дереве. А если чижей и деревьев [latex]n[/latex]?

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

[latex]n[/latex] – количество деревьев.

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

«Yes» или «No».

Тесты

Входные данные	Выходные данные
10	No
15	Yes

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

Код программы на С++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n%2==0) {
        cout << "No";
    } else {
        cout << "Yes";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

if (n%2==0) {

cout << "No";

} else {

cout << "Yes";

}

return 0;

}

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

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int n;
        Scanner in = new Scanner(System.in);
            
        n = in.nextInt();
        
        if (n%2==0) {
                System.out.println("No");
        }
        else {
                System.out.println("Yes");
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

if (n%2==0) {

System.out.println("No");

}

else {

System.out.println("Yes");

}

Решение

Решаем задачу сразу для [latex]n[/latex] чижей и [latex]n[/latex] деревьев. Обозначим количество чижей на [latex]k[/latex]-м дереве в какой-нибудь момент времени через [latex]a_{k}[/latex] (на первом дереве – [latex]a_{1} [/latex], на втором – [latex]a_{2}[/latex] и т.д.). Рассмотрим выражение [latex]S=1a_{1}+2a_{2}+\ldots+ka_{k}+\ldots+na_{n}[/latex]. Когда два чижа перелетают на соседние деревья в противоположных направлениях, то [latex]S[/latex] либо не меняется, либо меняется на [latex]n[/latex].
Действительно, пусть какой-то один чиж перелетает с [latex]k[/latex]-го дерева на следующее по часовой стрелке. Тогда в сумме [latex]S[/latex] меняются два слагаемых. Если [latex]k<n[/latex], то меняются [latex]k-1[/latex] и [latex]k+1[/latex] — е слагаемые, и их сумма становится равной [latex]k(a_{k}-1)+(k+1)(a_{k+1}+1)=ka_{k}+(k+1)a_{k+1}+1[/latex], то есть увеличивается нa 1. Если [latex]k=n[/latex], то меняется [latex]n[/latex] -е и первое слагаемые, а их сумма [latex]n(a_{n}-1)+1(a_{1}+1)=na_{n}+a_{1}-(n-1)[/latex] уменьшается на [latex]n-1[/latex]. Наоборот, если чиж перелетает на соседнее дерево против часовой стрелки, то сумма или уменьшается на 1, или увеличивается на [latex]n-1[/latex]. Поэтому, когда два чижа одновременно перелетают на соседние деревья (один по часовой стрелки, другой — против), то сумма [latex]S[/latex] или не меняется вовсе, или меняется на [latex]n[/latex]. В начальный момент времени на каждом дереве сидело по одному чижу, [latex]S=1\cdot1+2\cdot1+\ldots+n\cdot1=1+2+\ldots+n=\frac{n\left(n+1\right)}{2}[/latex].
Таким образом, после любого числа перелетов сумма будет равна [latex]\frac{n(n + 1)}{2} + np[/latex], где [latex]p[/latex] – некоторое целое число. Если бы все чижи собрались на каком-то одном [latex]q[/latex]-дереве, то [latex]S[/latex] было бы равно [latex]nq[/latex], то есть выполнялось бы равенство [latex]\frac{n(n + 1)}{2} + np = nq[/latex], откуда [latex]n + 1 + 2p = 2q[/latex], [latex]n=2(q-p)-1[/latex].
Таким образом, если [latex]n[/latex] четно, например, [latex]n[/latex] = 44, то чижи не смогут собраться на одном дереве. Покажем, что при нечетных [latex]n[/latex] это может случиться.
Рассмотрим исходную ситуацию, когда на каждом дереве сидело по одному чижу. «Прикажем» одному чижу сидеть на месте и назовем его «неподвижным». Разобьем оставшихся чижей на пары сидящих на одинаковом расстоянии в [latex]r[/latex] перелетов от неподвижного в ту и другую сторону ([latex]r=1,2,\ldots,\frac{n-1}{2}[/latex]).
Ясно, что каждая такая пара может за [latex]r[/latex] перелетов попасть на то дерево, гдe сидит неподвижный чиж.
Приведенное решение типично для задач, в которых требуется выяснить, можно ли в результате ряда каких-то преобразований получить определенный результат. В данном случае преобразование – это перелет двух чижей в противоположных направлениях, и мы хотим выяснить, могут ли в результате все чижи собраться на одном дереве. Чтобы доказать, что можно, достаточно привести пример, как это делать. Доказать, что ни при каких преобразованиях нельзя получить требуемый результат, часто бывает удобно так: найти какую-то величину, которая сохраняется при всех рассматриваемых преобразованиях и для которой начальное значение отличается от требуемого в конечном состоянии (такая величина называется инвариантом данных преобразований). В нашей задаче такой величиной является остаток от деления суммы [latex]S[/latex] на [latex]n[/latex].

Ссылка: Условие задачи
Ccылка: Решение задачи на сайте Ideone.com (C++)
Ccылка: Решение задачи на сайте Ideone.com (Java)

Related Images:

А58б. Нахождение значения функции

28/09/2016 by Эммануил Прокопов

Задача. Дано действительное число [latex]a[/latex]. Для функций [latex]f\left( x \right)[/latex], графики которых представлены на рис. 1,а-1,г, вычислить [latex]f\left( a \right) [/latex].

Тесты.

[latex]a[/latex]	[latex]y[/latex]
-1	1
0	0
2	4
-2	0.25
1.6	2.56
7	4

Код программы (C++).

#include <iostream>
using namespace std;
 
int main() {
    double a, y;
    cin >> a;
    if (a<-1)
    {
        y = 1/(a*a);
    }
    else
    {
        if (a>=-1 && a<=2)
        {
             y = a*a;
        }
        else
        {
            y = 4;
        }
    }
    cout << y;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double a, y;

cin >> a;

if (a<-1)

{

y = 1/(a*a);

}

else

{

if (a>=-1 && a<=2)

{

y = a*a;

}

else

{

y = 4;

}

cout << y;

return 0;

}

Код программы (Java).

import java.util.*;
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        double a, y;
        a = in.nextDouble();
        if (a < -1){
            y = 1/(a*a);
        }
        else{
            if (a >= -1 && a <= 2) y = a*a;
            else y = 4;
        }
        System.out.printf("%.8f\n", y);
    }
}

import java.util.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double a, y;

a = in.nextDouble();

if (a < -1){

y = 1/(a*a);

}

else{

if (a >= -1 && a <= 2) y = a*a;

else y = 4;

}

System.out.printf("%.8f\n", y);

}

Решение.
На графике функции указано, чему равна [latex]f\left( x \right)[/latex] на каждом участке. В данной программе мы по очереди проверяем, какому из них принадлежит [latex]f\left( a \right)[/latex] и выбираем соответствующую формулу для расчёта [latex]y[/latex]. Поскольку участков всего три, достаточно проверить, принадлежит ли точка к двум из них. Ели нет, то она, очевидно, лежит на третьем.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).

Related Images:

Числа Фибоначчи

18/09/2016 by Мазурок Игорь Евгеньевич

Рассмотрим общеизвестный ряд чисел A000045:
[latex]0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots[/latex] Этот ряд представляет собой неотрицательную ветвь последовательности Фибоначчи. Будем считать, что последовательность задаётся следующим рекуррентным соотношением
[latex]f_n=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
f_{n-1}+f_{n-2}, & n>1
\end{matrix}\right.[/latex]

Давайте напишем функцию, которая вычисляет [latex]n[/latex]-е по порядку число Фибоначчи, используя приведенное соотношение:

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

unsigned long long f (unsigned short n) {
    return n < 2? n : f(n-1) + f(n-2);
}

int main() {
    cout << f(6);
    return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

unsigned long long f (unsigned short n) {

return n < 2? n : f(n-1) + f(n-2);

}

int main() {

cout << f(6);

return 0;

}

Для теста мы вывели на печать вычисленное этим способом 6-е по порядку число Фибоначчи. Программа напечатала 8. И не ошиблась. Давайте посмотрим как происходили вызовы функций:

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Легко видеть, что для вычисления каждого числа Фибоначчи (кроме двух первых) выполняется строго два вызова функции. Т.е. если нам понадобится вычислить, следующее (седьмое) число Фибоначчи, то количество вызовов практически удвоится. И действительно, каждое следующее число вычисляется вдвое дольше, чем предыдущее. При наличии терпения ещё можно как-то дождаться конца вычисления 50-го числа, но дальше вычисляется уж очень долго.
В чём причина? Почему человек, вычисляя на листе бумаги, легко обгоняет компьютер?
Конечно, неэффективный алгоритм.
На рисунке цветом выделены те блоки, вычисление которых действительно необходимо. Число таких блоков растёт с увеличением номера числа линейно, говорят [latex]O\left( n\right)[/latex]. А вот остальные блоки — сплошные повторы и их число растёт как [latex]O\left( 2^n\right)[/latex].
Попробуйте изменить программу так, чтобы она работала быстро (без повторных вычислений.
В качестве упражнения, я попрошу не использовать циклов.
После того, как у Вас всё получится (или окончательно опустятся руки), загляните под спойлер и постарайтесь разобраться с моим вариантом решения задачи.

Рекурсивное решение без повторов

#include <iostream>
using namespace std;

unsigned long long tomorrow (
		unsigned short n, 
		unsigned long long yesterday, 
		unsigned long long today) 
{
	return n == 0? today : tomorrow(n - 1, today, yesterday + today);
}

unsigned long long h (unsigned short n) {
	return tomorrow (n, 0, 1);
}

int main() {
	cout<< f(93) << endl;
	return 0;
}