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

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

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

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

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

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

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

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

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

Mif 11

15/09/2016 by Станислав Коциевский

Задача

Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин на плоскости.

Тесты

Входные данные	Результат работы программы
1 1 1 7 5 3 1 6	0
5 6 8 8 2 2 5 4	2
1 -1 1 -3 2 -2 4 -1	1
-5 -1 -5 -3 -2 -1 -3 -2	2
-1 1 -1 3 -4 2 -3 5	2.52982
1 4 3 6 3 4 5 4	1.41421

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

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

struct point //точка
{
    double x;
    double y;
};
struct straight //прямая в виде общего уравнения Ax + By + C = 0
{
    double A;
    double B;
    double C;
};
straight create_straight (point A, point B)
{
    straight s;
    s.A = A.y - B.y;
    s.B = B.x - A.x;
    s.C = A.x * B.y - B.x * A.y;
    return s;
}
double r (point A, point B) //расстояние между двумя точками
{
    return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));
}
point projection (point A, point B, point C) // проекция точки С на прямую AB
{
    double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB
    double y = A.x - B.x;
    double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));
    point H;
    H.x = C.x + x * L;
    H.y = C.y + y * L;
    return H;
}
point intersection (straight a, straight b) //точка пересечения прямых a и b
{
    point ans;
    ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);
    ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);
    return ans;
}
void check_projection (point A, point B, point C, double & min_dis)
{
    point H = projection(A,B,C);
    if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку
    {
        if (r(H,C) < min_dis)
        {
            min_dis = r(H,C);
        }
    }
}
double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются
{
    double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));
    check_projection (A,B,C,min_dis);
    check_projection (A,B,D,min_dis);
    check_projection (C,D,A,min_dis);
    check_projection (C,D,B,min_dis);
    return min_dis;
}
int main()
{
    point A,B,C,D;
    cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;
    straight AB = create_straight(A,B);
    straight CD = create_straight(C,D);
    if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых
    {
        cout<<distance_if_not_intersect(A,B,C,D);
    }
    else
    {
        point H = intersection(AB,CD);
        if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам
        (H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )
        {
            cout<<0;
        }
        else
        {
            cout<<distance_if_not_intersect(A,B,C,D);
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

struct point //точка

{

double x;

double y;

};

struct straight //прямая в виде общего уравнения Ax + By + C = 0

{

double A;

double B;

double C;

};

straight create_straight (point A, point B)

{

straight s;

s.A = A.y - B.y;

s.B = B.x - A.x;

s.C = A.x * B.y - B.x * A.y;

return s;

}

double r (point A, point B) //расстояние между двумя точками

{

return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));

}

point projection (point A, point B, point C) // проекция точки С на прямую AB

{

double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB

double y = A.x - B.x;

double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));

point H;

H.x = C.x + x * L;

H.y = C.y + y * L;

return H;

}

point intersection (straight a, straight b) //точка пересечения прямых a и b

{

point ans;

ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);

ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);

return ans;

}

void check_projection (point A, point B, point C, double & min_dis)

{

point H = projection(A,B,C);

if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку

{

if (r(H,C) < min_dis)

{

min_dis = r(H,C);

}

double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются

{

double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));

check_projection (A,B,C,min_dis);

check_projection (A,B,D,min_dis);

check_projection (C,D,A,min_dis);

check_projection (C,D,B,min_dis);

return min_dis;

}

int main()

{

point A,B,C,D;

cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;

straight AB = create_straight(A,B);

straight CD = create_straight(C,D);

if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых

{

cout<<distance_if_not_intersect(A,B,C,D);

}

else

{

point H = intersection(AB,CD);

if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам

(H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )

{

cout<<0;

}

else

{

cout<<distance_if_not_intersect(A,B,C,D);

}

return 0;

}

Решение

Основная идея состоит в том, что расстояние между непересекающимися отрезками [latex]AB[/latex] и [latex]CD[/latex] — это минимальная из длин, соединяющих вершины разных отрезков, и длин перпендикуляров, проведенных из вершины на противоположный отрезок. Подробнее о математической части поиска перпендикуляра тут. Кроме этого, отрезки могут пересекаться, что проверяется отдельно. В таком случае, расстояние между ними равно нулю.

Чтобы проверить, пересекаются ли отрезки, нужно сначала проверить, не параллельны ли они.Если они не параллельны, нужно найти точку пересечения прямых, на которых лежат отрезки, а затем проверить принадлежит ли она обоим отрезкам. Отрезки пересекаются тогда и только тогда, когда они лежат на пересекающихся прямых, точка пересечения которых принадлежит обоим отрезкам. Координаты точки пересечения находятся из системы уравнений прямых, на которых лежат отрезки.
[latex] \begin{cases} A_{1}x + B_{1}y + C_{1} = 0 \\ A_{2}x + B_{2}y + C_{2} = 0 \end{cases} [/latex]

Из первого уравнения: [latex]x = \frac{-B_{1}y-C_{1}}{A_{1}}[/latex]

Подставим [latex]x[/latex] во второе уравнение:

[latex] \frac{A_{2}}{A_{1}}(-B_{1}y-C_{1}) + B_{2}y + C_{2} = 0[/latex] [latex](*)[/latex]

Решив уравнение [latex](*)[/latex] получим:

[latex]y = \frac{C_{1}A_{2}-C_{2}A_{1}}{A_{1}B_{2}-A_{2}B_{1}}[/latex].

Тогда

[latex]x = \frac{C_{2}B_{1}-C_{1}B_{2}}{A_{1}B_{2}-A_{2}B_{1}}[/latex]

Ссылка на код на ideone

Related Images:

AL1

13/09/2016 by Станислав Коциевский

Условие задачи

Вводится последовательность, состоящая из [latex]N[/latex] пар символов [latex](a_i, b_i)[/latex]. Каждая пара определяет порядок предшествования символов, например, пара [latex](b, c)[/latex] означает, что символ [latex]b[/latex] предшествует символу [latex]c[/latex]. Из порядка [latex](b, c)[/latex] и [latex](c, a)[/latex] следует порядок [latex](b, a)[/latex]. Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку [latex]A_{1},A_{2}, \cdots ,A_{s}[/latex] в порядке предшествования;

б) противоречивой, т.е. для некоторых символов [latex]x,y[/latex] можно получить одновременно порядок как [latex](x, y)[/latex] так и [latex](y, x)[/latex];

Тесты

Входные данные	Результат
4 a b b c c d b d	полный порядок
3 2 a 8 c c b	порядок неполный
3 2 a 8 c a 8	полный порядок
4 2 a 8 c c 2 a c	Порядок противоречив
10 a 5 5 4 b 3 3 4 5 3 b 5 a b 4 * * 0 4 0	полный порядок

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

#include <iostream>
#include <algorithm> //для использования функции sort
using namespace std;

int main()
{
    const int lch = 256;
    int n;
    cin>>n;
    
    char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.
    for (int i = 0; i < n; i++)
    {
        p[i] = new char [2];
    }
        
    for (int i = 0; i < n; i++)
    {
        cin >> p[i][1]>>p[i][2];
    }
    
    int chars[lch];
    for (int i = 0; i<lch; i++)
    {
        chars[i] = -1;
    }
    int K = 0;
    for (int i = 0; i<n; i++)
    {
        if (chars [ p[i][1]] == -1)
            K++;
        if (chars [ p[i][2]] == -1)
            K++;
        chars [ p[i][1]] = 0;
        chars [ p[i][2]] = 0;
    }
    
    bool change;
    char x, y;
    int M;
    for (int i = 0; i < n; i++)
    {
        change = false;
        for (int j = 0; j < n; j++)
        {
            x = p[j][1];
            y = p[j][2];
            M = max(chars[x] + 1, chars [y]);
            if (M > (K-1))
            {
                cout<<"Порядок противоречив";
                return 0;
            }
            if (chars[y] != M)
            {
                change = true;
            }
            chars[y] = M;
        }
        if (!change)
        {
            sort(chars, chars+lch);
            int previous = K;
            int i = lch-1;
            while (chars [i] > -1)
            {
                if (chars[i] == previous - 1)
                {
                    previous--;
                }
                else
                {
                    cout<<"порядок неполный";
                    return 0;
                }
                i--;
            }
            cout<<"полный порядок";
            return 0;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm> //для использования функции sort

using namespace std;

int main()

{

const int lch = 256;

int n;

cin>>n;

char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.

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

{

p[i] = new char [2];

}

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

{

cin >> p[i][1]>>p[i][2];

}

int chars[lch];

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

{

chars[i] = -1;

}

int K = 0;

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

{

if (chars [ p[i][1]] == -1)

K++;

if (chars [ p[i][2]] == -1)

K++;

chars [ p[i][1]] = 0;

chars [ p[i][2]] = 0;

}

bool change;

char x, y;

int M;

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

{

change = false;

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

{

x = p[j][1];

y = p[j][2];

M = max(chars[x] + 1, chars [y]);

if (M > (K-1))

{

cout<<"Порядок противоречив";

return 0;

}

if (chars[y] != M)

{

change = true;

}

chars[y] = M;

}

if (!change)

{

sort(chars, chars+lch);

int previous = K;

int i = lch-1;

while (chars [i] > -1)

{

if (chars[i] == previous - 1)

{

previous--;

}

else

{

cout<<"порядок неполный";

return 0;

}

i--;

}

cout<<"полный порядок";

return 0;

}

return 0;

}

Решение

Общая идея решения

Эта часть решения взята отсюда.

Пусть при записи этих [latex]N[/latex] пар встретилось всего [latex]K[/latex] различных символов, которые образуют множество [latex]X[/latex].

Идея решения задачи состоит в последовательном присвоении каждому символу [latex]s[/latex] из [latex]X[/latex] номера, который определяет количество [latex]P(s)[/latex] элементов, предшествующих ему, с учетом свойства транзитивности (из [latex](c, b)[/latex] и [latex](b, a)[/latex] следует [latex](c, a)[/latex]). Это осуществляется следующим образом:

Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. [latex]P(s)=0[/latex] для любого [latex]s[/latex].

При просмотре очередной пары [latex](x, y)[/latex] символу y присваивается большее из значений [latex]P(x)+1, P(y)[/latex].

Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2, т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров входной строки возможно несколько вариантов.

Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до [latex]K-1[/latex], то эта нумерация определяет полный порядок. Иначе порядок неполный.
Номер некоторого символа превысил [latex]K-1[/latex]. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.

Легко понять, что число просмотров не превысит [latex]N[/latex].

Некоторые аспекты реализации

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

Воспользуемся тем фактом, что символы воспринимаются компьютером, как числа. Заведем для номеров символов в последовательности массив chars на 256 элементов, поскольку тип данных char может принимать значения от 0 до 255. Это позволит обращаться к элементу массива, соответствующий какому-то символу напрямую, а не используя ассоциативный массив. Это дает выигрыш в скорости, хотя и с некоторым увеличением расхода памяти.

Изначально каждый элемент массива chars пусть будет равен -1. Затем, пройдя все пары, присвоим каждому символу номер 0 в этом массиве. Таким образом, мы в дальнейшем сможем определить, что символ входит в нашу последовательность, поскольку его номер неотрицательный.

Если при очередном просмотре входной строки не произошло изменений, отсортируем массив номеров и проверим каждый ли предыдущий неотрицательный меньше следующего на 1.

ссылка на код на ideone

ссылка на условие задачи

Related Images:

Лабиринт

02/07/2016 by Маша Лукьянова

Условие:

Имя входного файла: стандартный поток ввода

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 2 second

Ограничение по памяти: 64 мегабайт

Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Задача взята из 1-го раунда KPI OPEN 2013 года.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq N \leq 100) $$ и $$k (0 \leq k \leq 10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k (0 \leq k \leq 10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

В единственной строке выходного файла выведите единственное целое число не меньше нуля — наименьшее количество передвижений по пути, после которого можно точно определить местоположение робота. Если ответ не существует, либо входные данные некорректны, выведите -1.

Тесты:

№	Входные данные	Выходные данные
1	2 0 11 01	0
2	2 0 11 11	-1
3	2 1 11 01 R	-1
4	3 3 000 010 000 RDU	2
5	5 5 00010 10001 00100 10100 01101 RDUUU	4

Решение:

Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них $$ 10^{5} $$ ходов, что в результате дает $$ 10^{9} $$ операций.

Решение «в лоб»:

Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:
- Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.
- Иначе ничего не делаем.
Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.
Так будем делать до тех пор, пока робот закончил свой путь.
Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 1 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <set>
#include <list>
#include <map>
 
#define ll long long int
#define X first
#define Y second
#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    char maze[n][n];//лабиринт
    for(int i = 0; i < n; ++i){
        getchar();
        for(int j = 0; j < n; ++j){
            maze[i][j] = getchar();
        }
    }
    getchar();
    char path[k+1]; //путь
    for(int i = 0; i < k; ++i){
        path[i + 1] = getchar();
    }
    set<pair<int, int> > visited; 
        //ячейки, в которых мы побывали
    map<int, pair<int, int> > nodes; 
        // узлы, которые должен пройти робот (номер хода, координаты)
    pair<int, int> cur = {0, 0};
    visited.insert(cur);
    nodes[0] = cur; 
    //проходим весь путь
    for(int i = 1; i <= k; ++i){
        if(path[i] == 'L'){
            --cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'R'){
            ++cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'U'){
            --cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'D'){
            ++cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }
    }
    int count = 0;
    map<int, int> ans; bool ok = false;
    for(; nodes.size();){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                for(pair<int, pair<int, int> > a : nodes){
                    if(j + a.Y.X < 0 || j + a.Y.X >= n ||
                              // не вышли ли за пределы по строкам
                        i + a.Y.Y < 0 || i + a.Y.Y >= n || 
                              // не вышли ли за пределы по столбцам
                        maze[i + a.Y.Y][j + a.Y.X] == '1'){ 
                              //не попали ли на 1-цу
                        --count;
                        break;
                    }
                }
                ++count;
            }
        }
        auto t = --nodes.end();
        ans[count] = t->X;
        nodes.erase(t);
        count = 0;
        if(ans.size() == 2) break;
        if(!ok){
            ok = 1;
            if(ans.begin()->X != 1){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    if(ans.size() == 1 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else if(ans.size() == 2 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else{
        cout << -1 << endl;
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <stack>

#include <set>

#include <list>

#include <map>

#define ll long long int

#define X first

#define Y second

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

char maze[n][n];//лабиринт

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

getchar();

for(int j = 0; j < n; ++j){

maze[i][j] = getchar();

}

getchar();

char path[k+1]; //путь

for(int i = 0; i < k; ++i){

path[i + 1] = getchar();

}

set<pair<int, int> > visited;

//ячейки, в которых мы побывали

map<int, pair<int, int> > nodes;

// узлы, которые должен пройти робот (номер хода, координаты)

pair<int, int> cur = {0, 0};

visited.insert(cur);

nodes[0] = cur;

//проходим весь путь

for(int i = 1; i <= k; ++i){

if(path[i] == 'L'){

--cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'R'){

++cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'U'){

--cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'D'){

++cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

int count = 0;

map<int, int> ans; bool ok = false;

for(; nodes.size();){

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

for(int j = 0; j < n; ++j){

for(pair<int, pair<int, int> > a : nodes){

if(j + a.Y.X < 0 || j + a.Y.X >= n ||

// не вышли ли за пределы по строкам

i + a.Y.Y < 0 || i + a.Y.Y >= n ||

// не вышли ли за пределы по столбцам

maze[i + a.Y.Y][j + a.Y.X] == '1'){

//не попали ли на 1-цу

--count;

break;

}

++count;

}

auto t = --nodes.end();

ans[count] = t->X;

nodes.erase(t);

count = 0;

if(ans.size() == 2) break;

if(!ok){

ok = 1;

if(ans.begin()->X != 1){

cout << -1 << endl;

return 0;

}

if(ans.size() == 1 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else if(ans.size() == 2 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else{

cout << -1 << endl;

}

Submission.

Related Images:

A299

26/03/2016 by Сплошнов Кирилл

Условие

Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся стандартным классом vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией min_element() или max_element() (библиотека algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

№	Входные данные	Выходные данные
1	-2 2 43 5 -10 12 0 -1	-3698 3698 79507 9245 -18490 22188 0 -1849
2	0 100 99 0 -1 1	0 100 99 0 -1 1
3	42 1 1 1 0 -1 24 -24 -42	74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
	vector<int> x;
	int a;
	while (cin >> a)
		x.push_back(a);
	if (x.at(0) >= 0)
	{
		int min = *min_element(x.begin(), x.end());
		for (int &i : x)
			i *= min * min;
	}
	else
	{
		int max = *max_element(x.begin(), x.end());
		for (int &i : x)
			i *= max * max;
	}
	for (int i : x)
		cout << i << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<int> x;

int a;

while (cin >> a)

x.push_back(a);

if (x.at(0) >= 0)

{

int min = *min_element(x.begin(), x.end());

for (int &i : x)

i *= min * min;

}

else

{

int max = *max_element(x.begin(), x.end());

for (int &i : x)

i *= max * max;

}

for (int i : x)

cout << i << " ";

return 0;

}

Замечание

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

Ссылки

Код на ideaone (vector).

Related Images:

А57в

26/12/2015 by Кирилл Демиденко

Задача

Дано действительное число [latex] a [/latex] . Вычислить [latex]f\left ( a \right )[/latex], если [latex]f\left ( x \right )=\left\{\begin{matrix} 0, x\leq 0 \\ x, 0< x\leq 1\\ x^{4}, x> 1 \end{matrix}\right.[/latex]

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

int main() {
    int x;
    cin >> x;
    if (x <= 0){
        cout << 0;
    }
    if (x > 0 && x <=1){
        cout << x;
    }
    if (x > 1){
        cout << pow(x,4);
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int x;

cin >> x;

if (x <= 0){

cout << 0;

}

if (x > 0 && x <=1){

cout << x;

}

if (x > 1){

cout << pow(x,4);

}

return 0;

}

Вводим действительное число [latex]x[/latex]. Если число меньше 0, то программа выводит 0. Если в промежутке от 0 до 1 включительно, то выводит введенное число. Если же число больше 1, то возводит его в четвертую степень.

Related Images:

Mif 18

20/12/2015 by Таня Корнилова

Задача Mif 18.

Условие

Введите из стандартного потока целое число и выведите его словами на английском языке.

Тесты

Входные данные	Выходные данные
0	zero
-7284	minus seven thousand two hundred and eighty-four
900000000000000010	nine hundred billiard ten
4561230057773	four billion five hundred and sixty-one milliard two hundred and thirty million fifty-seven thousand seven hundred and seventy-three
599999990999999900	five hundred and ninety-nine billiard nine hundred and ninety-nine billion nine hundred and ninety milliard nine hundred and ninety-nine million nine hundred and ninety-nine thousand nine hundred

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

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

void number (long long n) {
	if(abs(n) < 1000){// сотни, десятки, единицы
		if(n < 0) { 
			cout << "minus ";
			n = abs(n);
			number(n);
		} 
		else if(n == 0) cout << "zero";
		else {// натуральные числа
			int safe = n;// сохраняем значение числа, так как дальше его изменяем,
			if((n / 100) != 0) {// если есть сотни
				n = n / 100;
			}
			switch(n){
				case 1: cout << "one "; break; 
				case 2: cout << "two "; break; 
				case 3: cout << "three "; break; 
				case 4: cout << "four "; break; 
				case 5: cout << "five "; break;
				case 6: cout << "six "; break; 
				case 7: cout << "seven "; break; 
				case 8: cout << "eight "; break; 
				case 9: cout << "nine "; break; 
			}
			if(((safe / 100) == 0) && ((safe % 100) / 10 == 0)){
				n = -1e90;// чтобы не продолжать выводить нули
			}
			if((safe / 100) > 0) {
				cout << "hundred ";
				n = safe % 100;
				safe = 0;
				if(n > 0){
				cout << "and ";
				}
			}
			if((n / 10) == 0){
				number(n);
			} else if((n / 10) == 1) {
				switch(n) {
					case 10: cout << "ten "; break;
					case 11: cout << "eleven "; break;
					case 12: cout << "twelve "; break;
					case 13: cout << "thirteen "; break;
					case 14: cout << "fourteen "; break;
					case 15: cout << "fifteen "; break;
					case 16: cout << "sixteen "; break;
					case 17: cout << "seventeen "; break;
					case 18: cout << "eighteen "; break;
					case 19: cout << "nineteen "; break;
				}
			} else if((n / 10) > 1) {
				switch(n / 10) {
					case 2: cout << "twenty"; break; 
					case 3: cout << "thirty"; break; 
					case 4: cout << "forty"; break; 
					case 5: cout << "fifty"; break;
					case 6: cout << "sixty"; break; 
					case 7: cout << "seventy"; break; 
					case 8: cout << "eighty"; break; 
					case 9: cout << "ninety"; break;
				}
				n = n % 10;
				if(n != 0){
					cout << "-";
					number(n);
				}
			} 
		}
	} else {// выводим тысячи, миллионы, миллиарды и т.д.	
		if(n >= 1e15) {
			number(n / 1e15);
			cout << "billiard ";
			n %= (long long) 1e15;
			if(n != 0) number(n);
		} else if(n >= 1e12) {
			number(n / 1e12);
			cout << "billion ";
			n %= (long long) 1e12;
			if(n != 0) number(n);
		} else if(n >= 1e9) {
			number(n / 1e9);
			cout << "milliard ";
			n %= (int) 1e9;
			if(n != 0) number(n);
		} else if(n >= 1e6) {
			number(n / 1e6);
			cout << "million ";
			n %= (int) 1e6;
			if(n != 0) number(n);
		} else if(n >= 1e3) {
			number(n / 1e3);
			cout << "thousand ";
			n %= (int) 1e3;
			if(n != 0) number(n);// чтоб не выводить ноль после тысяч
		}
	}
}



int main() {
	long long n;
	cin >> n;
	number(n);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include <iostream>

#include <cmath>

using namespace std;

void number (long long n) {

if(abs(n) < 1000){// сотни, десятки, единицы

if(n < 0) {

cout << "minus ";

n = abs(n);

number(n);

}

else if(n == 0) cout << "zero";

else {// натуральные числа

int safe = n;// сохраняем значение числа, так как дальше его изменяем,

if((n / 100) != 0) {// если есть сотни

n = n / 100;

}

switch(n){

case 1: cout << "one "; break;

case 2: cout << "two "; break;

case 3: cout << "three "; break;

case 4: cout << "four "; break;

case 5: cout << "five "; break;

case 6: cout << "six "; break;

case 7: cout << "seven "; break;

case 8: cout << "eight "; break;

case 9: cout << "nine "; break;

}

if(((safe / 100) == 0) && ((safe % 100) / 10 == 0)){

n = -1e90;// чтобы не продолжать выводить нули

}

if((safe / 100) > 0) {

cout << "hundred ";

n = safe % 100;

safe = 0;

if(n > 0){

cout << "and ";

}

if((n / 10) == 0){

number(n);

} else if((n / 10) == 1) {

switch(n) {

case 10: cout << "ten "; break;

case 11: cout << "eleven "; break;

case 12: cout << "twelve "; break;

case 13: cout << "thirteen "; break;

case 14: cout << "fourteen "; break;

case 15: cout << "fifteen "; break;

case 16: cout << "sixteen "; break;

case 17: cout << "seventeen "; break;

case 18: cout << "eighteen "; break;

case 19: cout << "nineteen "; break;

}

} else if((n / 10) > 1) {

switch(n / 10) {

case 2: cout << "twenty"; break;

case 3: cout << "thirty"; break;

case 4: cout << "forty"; break;

case 5: cout << "fifty"; break;

case 6: cout << "sixty"; break;

case 7: cout << "seventy"; break;

case 8: cout << "eighty"; break;

case 9: cout << "ninety"; break;

}

n = n % 10;

if(n != 0){

cout << "-";

number(n);

}

} else {// выводим тысячи, миллионы, миллиарды и т.д.

if(n >= 1e15) {

number(n / 1e15);

cout << "billiard ";

n %= (long long) 1e15;

if(n != 0) number(n);

} else if(n >= 1e12) {

number(n / 1e12);

cout << "billion ";

n %= (long long) 1e12;

if(n != 0) number(n);

} else if(n >= 1e9) {

number(n / 1e9);

cout << "milliard ";

n %= (int) 1e9;

if(n != 0) number(n);

} else if(n >= 1e6) {

number(n / 1e6);

cout << "million ";

n %= (int) 1e6;

if(n != 0) number(n);

} else if(n >= 1e3) {

number(n / 1e3);

cout << "thousand ";

n %= (int) 1e3;

if(n != 0) number(n);// чтоб не выводить ноль после тысяч

}

int main() {

long long n;

cin >> n;

number(n);

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Данная программа выводит число «по частям», то есть вначале триллионы, затем биллиарды, биллионы и т.д. до единиц (за условием их наличия). Если число отрицательное, то она выводит «минус» и его абсолютную величину.

При выполнениии задания я воспользовалась длинной шкалой наименования чисел.

Программа выводит целые числа в промежутке [latex](-10^{19}; 10^{19})[/latex].

Related Images:

acm.timus.ru №2002. Тестовое задание

04/12/2015 by Марченко Філіп Олександрович

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время:	0.5 секунды
Память	64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…

Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!

Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:

«register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
«login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
«logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».

Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!

И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq{n}\leq100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные

Результат

logout vasya

success: new user added

fail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Решение

Для решения данной задачи нам необходимо воспользоваться структурой данных, которая хранит в себе пары вида «ключ — значение», а также структурой, которая будет хранить в себе некоторое множество. Воспользуемся структурами HashMap (Java) / map (C++) (key -> value) и HashSet (множество).

Рассмотрим операции, которые должна уметь обрабатывать наша система:

«register username password». При регистрации нового пользователя будем помещать его в нашу «базу» зарегистрированных пользователей при условии, что он не зарегистрирован. Поиском по ключу в HashMap / map проверим существование уже зарегистрированного никнейма. Если найдётся такой пользователь, то система выдаст сообщение об ошибке.
«login user password». Если база пользователей содержит в себе логин пользователя, пароли совпадают и пользователь не в он-лайне, то система разрешит user’у вход на форум. В противном случае, с соответствующими сообщениями об ошибках, не разрешит вход. Отслеживать пользователей, которые уже online, будем с помощью HashSet. Если пользователя нет в базе пользователей, которые сейчас на сайте, то открывая доступ, система поместит его в базу-online. Тогда новый запрос login с этого ника будет отклонён.
«logout name». Если пользователя нет в базе пользователей, то его logout невозможен. Иначе, если его нет в базе-online, то тоже система выдаст сообщение об ошибке. Если user есть в базе пользователей и находится в онлайне, то выход возможен. Во время logouta удаляем пользователя из базы-online.

Реализация

В данном отчёте задачи будут представлены на языках Java и C++. Опишем, для начала, какие классы и методы необходимо использовать для решения этой задачи на языке Java:

HashMap:

Будем использовать интерфейс Map, имплементация (реализация) — HashMap. Из интерфейса Map воспользуемся следующими методами:

containsKey(Key K) — возвращает true, если ключ найден. В противном случае — false;
put(Key K, Value V) — записывает пару ключ-значение в структуру;
get(Key K) — по ключу возвращает значение.

HashSet:

Используем интерфейс Set, реализация — HashSet. Будем использовать следующие методы:

contains(Object o) — возвращает true, если элемент принадлежит множеству. Иначе — false;
add(Object o) — добавляет элемент во множество;
remove(Object o) — удаляет элемент из множества.

Теперь для С++:

В С++ воспользуемся немного другим подходом. Воспользуемся только map. Создадим структуру, которая будет содержать 2 поля: пароль и статус. Воспользуемся следующими методами:

find (K key) — возвращает итератор элемента.
end() — возвращает итератор за последним элементом.

set или без него?

Для данной задачи использование set’a не принципиально. Но если предположить, что, помимо запросов регистрации, входа и выхода, был бы ещё и запрос вывести пользователей, которые онлайн, преимущество использования set’a очевидно.

Код на Java:

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

 class Ideone {
    public static void main (String[] args) {
        
        //create an DB for online and reged users
        Map DB = new HashMap<String, String> (); 
        HashSet <String> DBin = new HashSet <String> ();
        
        Scanner in = new Scanner (System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        //a number of queries
        int n = in.nextInt();
        
        
        for (int i = 0; i < n; i++){
            String s, log, pass;
            
            //command
            s = in.next();
            
            if (s.equals("register")){
                log = in.next();    //login
                pass = in.next();   //password
                if (DB.containsKey(log)){   //login in DB?
                    out.println("fail: user already exists");
                    out.flush();
                }
                else {
                    DB.put(log, pass);
                    out.println("success: new user added");
                    out.flush();
                }
            }
            
            if (s.equals("login")){
                log = in.next();
                pass = in.next();
                if (DB.containsKey(log)){ //if user is reg
                    if (pass.equals(DB.get(log))) { //if the password is well
                        if (!DBin.contains(log)) {  //online?
                            DBin.add(log);
                            out.println("success: user logged in");
                            out.flush();
                        }
                        //Errors
                        else {
                            out.println("fail: already logged in");
                            out.flush();
                        }
                    }
                    else {
                        out.println("fail: incorrect password");
                        out.flush();
                    }
                }
                else {
                    out.println("fail: no such user");
                    out.flush();
                }
            }
            if (s.equals("logout")){
                log = in.next();
                if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.
                    out.println("fail: no such user");
                    out.flush();
                }
                else {
                    if (!DBin.contains(log)){   //so offline user does
                        out.println("fail: already logged out");
                        out.flush();
                    }
                    else {
                        DBin.remove(log);
                        out.println("success: user logged out");
                        out.flush();
                    }
                }
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

//create an DB for online and reged users

Map DB = new HashMap<String, String> ();

HashSet <String> DBin = new HashSet <String> ();

Scanner in = new Scanner (System.in);

PrintWriter out = new PrintWriter(System.out);

//a number of queries

int n = in.nextInt();

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

String s, log, pass;

//command

s = in.next();

if (s.equals("register")){

log = in.next(); //login

pass = in.next(); //password

if (DB.containsKey(log)){ //login in DB?

out.println("fail: user already exists");

out.flush();

}

else {

DB.put(log, pass);

out.println("success: new user added");

out.flush();

}

if (s.equals("login")){

log = in.next();

pass = in.next();

if (DB.containsKey(log)){ //if user is reg

if (pass.equals(DB.get(log))) { //if the password is well

if (!DBin.contains(log)) { //online?

DBin.add(log);

out.println("success: user logged in");

out.flush();

}

//Errors

else {

out.println("fail: already logged in");

out.flush();

}

else {

out.println("fail: incorrect password");

out.flush();

}

else {

out.println("fail: no such user");

out.flush();

}

if (s.equals("logout")){

log = in.next();

if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.

out.println("fail: no such user");

out.flush();

}

else {

if (!DBin.contains(log)){ //so offline user does

out.println("fail: already logged out");

out.flush();

}

else {

DBin.remove(log);

out.println("success: user logged out");

out.flush();

}

Код на С++:

#include <iostream>
#include <stdio.h>
#include <string>
#include <iomanip>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;

struct status { //status - password and online
    string password;
    bool online = false;
};

map <string, status> database; //user database


int main () {
    int n; cin >> n; //number of queries
    typedef std::map<std::string, status> db; // use this typedef for an iterator
    while (n--){
        string com, login; //command and login
        status query; //for status input
        cin >> com;
        if (com == "register"){
            cin >> login >> query.password;
            db::iterator it = database.find(login); //returning an iterator
            if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db
                cout << "fail: user already exists\n";
            }
            else {
                database[login].password = query.password; // register
                cout << "success: new user added\n";
            }
        }
        //user can log in if he isn't online but he is registered
        if (com == "login") {
            cin >> login >> query.password;
            db::iterator it = database.find(login);
            if (it != database.end()){
                if (query.password == database[login].password){
                    if(!database[login].online){
                        database[login].online = true;
                        cout << "success: user logged in\n";
                    }
                    else cout << "fail: already logged in\n";
                }
                else cout << "fail: incorrect password\n";
            }
            else cout << "fail: no such user\n";
        }
        //logout
        if (com == "logout") {
            cin >> login;
            if (database.find(login) == database.end()) cout << "fail: no such user\n";
            else {
                if (!database[login].online) cout << "fail: already logged out\n";
                else {

                    database[login].online = false;
                    cout << "success: user logged out\n";
                }
            }
        }
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <string>

#include <iomanip>

#include <stack>

#include <vector>

#include <algorithm>

#include <cmath>

#include <queue>

#include <map>

using namespace std;

struct status { //status - password and online

string password;

bool online = false;

};

map <string, status> database; //user database

int main () {

int n; cin >> n; //number of queries

typedef std::map<std::string, status> db; // use this typedef for an iterator

while (n--){

string com, login; //command and login

status query; //for status input

cin >> com;

if (com == "register"){

cin >> login >> query.password;

db::iterator it = database.find(login); //returning an iterator

if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db

cout << "fail: user already exists\n";

}

else {

database[login].password = query.password; // register

cout << "success: new user added\n";

}

//user can log in if he isn't online but he is registered

if (com == "login") {

cin >> login >> query.password;

db::iterator it = database.find(login);

if (it != database.end()){

if (query.password == database[login].password){

if(!database[login].online){

database[login].online = true;

cout << "success: user logged in\n";

}

else cout << "fail: already logged in\n";

}

else cout << "fail: incorrect password\n";

}

else cout << "fail: no such user\n";

}

//logout

if (com == "logout") {

cin >> login;

if (database.find(login) == database.end()) cout << "fail: no such user\n";

else {

if (!database[login].online) cout << "fail: already logged out\n";

else {

database[login].online = false;

cout << "success: user logged out\n";

}

return 0;

}

Результаты

Обе реализации прошли все тесты на Тимусе с такими результатами:

Язык	Время работы	Память
С++	0.015	412 КБ
Java	0.124	1 804 КБ

Ссылки

Related Images:

MLoops 23

01/11/2015 by Сплошнов Кирилл

Условие

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк):

0, 1, 8, 27, 64, 125, 216
, 343, 512, 729, 1000, 13
31, 1728, 2197, 2744, 337
5, 4096, 4913, 5832, 6859
, 8000, 9261, 10648, 1216
7, 13824, 15625, 17576, 1
9683, 21952, 24389, 27000
, 29791, 32768, 35937, 39

0, 1, 8, 27, 64, 125, 216

, 343, 512, 729, 1000, 13

31, 1728, 2197, 2744, 337

5, 4096, 4913, 5832, 6859

, 8000, 9261, 10648, 1216

7, 13824, 15625, 17576, 1

9683, 21952, 24389, 27000

, 29791, 32768, 35937, 39

Тесты

[latex]n \times {m}[/latex]	Выходные данные
[latex]2 \times {2}[/latex]	0, _1
[latex]2 \times {10}[/latex]	0, _1 , 8, _2 7, _6 4, _1 25
[latex]5 \times {5}[/latex]	0, 1, _8, 2 7, 64 , 125 , 216
[latex]20 \times {1}[/latex]	0, 1, 8, 27, 64, 125
[latex]22 \times {10}[/latex]	0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 10 00, 1331, 1728, 2197, 2744, 3375, 4096, 4913 , 5832, 6859, 8000, 92 61, 10648, 12167, 1382 4, 15625, 17576, 19683 , 21952, 24389, 27000, _29791, 32768, 35937, 39304, 42875, 46656, 5

(Нижние подчеркивания в таблице добавил намеренно, там, где строка начинается с пробела, так как они автоматически убирались.)

Решение

Нетрудно заметить, что данная последовательность содержит кубы натуральных чисел, разделенные запятой с пробелом (единственное отличие, первое число — ноль). Очевидно, понадобится использовать 2 цикла, внешний (для строк) и внутренний (для столбцов). Для простоты я попробовал составить алгоритм так, чтобы:

а) во внешнем цикле не было ничего, кроме перехода на новую строку;

б) за один шаг внутреннего цикла печатался ровно 1 символ.

Проанализируем ключевые моменты. Во первых, числа надо будет выводить по одной цифре за раз. Так как мы не знаем длину числа, можно воспользоваться функцией [latex]log10[/latex], но намного проще выводить число в обратном порядке (используя деление по модулю 10), поэтому при вычислении очередного куба будем сохранять его во временную переменную, а в печатаемую переменную [latex]cube[/latex] будем сохранять это число, записанное в обратном порядке, и выводить его на экран также в обратном порядке (таким образом, получая исходный порядок).

Как только число стало ноль, нужно вывести запятую, затем пробел. Запятую будем выводить сразу вместо очередной цифры числа, для пробела заведем логическую переменную [latex]addSpacebar[/latex], которую будем проверять вначале каждого шага внутреннего цикла.

Единственный недочет — числа вроде 1000, так как при инверсии получим 0001, то есть число 1. Я решил эту проблему, заведя переменную [latex]zeros[/latex], хранящую кол-во таких нулей. Начальное число ноль тоже учтено в коде (см. комментарии).

Код

#include <iostream>
using namespace std;

int main() 
{
	int n, m;
	cin >> n >> m;
	long num = 0, cube = 0;
	bool addSpacebar = false;
	int zeros = 0;
	for (int i = 0; i < m; i ++)
	{
		for (int j = 0; j < n; j ++)
		{
			if (addSpacebar) //если необходим пробел
			{
				cout << " ";
				addSpacebar = false;
			}
			else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0
			{
				cout << cube % 10;
				cube /= 10;
			}
			else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся
			{
				cout << 0;
				zeros --;
			}
			else //иначе
			{
				cout << ","; //печатаем запятую
				addSpacebar = true; //запоминаем, что нужен пробел
				num ++;
				long L = num * num * num; //получаем куб следующего числа
				while (L > 0) //записываем его в обратного порядке
				{
					cube *= 10;
					cube += L % 10;
					if (cube == 0) 
						zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)
					L /= 10;
				}
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m;

cin >> n >> m;

long num = 0, cube = 0;

bool addSpacebar = false;

int zeros = 0;

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

{

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

{

if (addSpacebar) //если необходим пробел

{

cout << " ";

addSpacebar = false;

}

else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0

{

cout << cube % 10;

cube /= 10;

}

else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся

{

cout << 0;

zeros --;

}

else //иначе

{

cout << ","; //печатаем запятую

addSpacebar = true; //запоминаем, что нужен пробел

num ++;

long L = num * num * num; //получаем куб следующего числа

while (L > 0) //записываем его в обратного порядке

{

cube *= 10;

cube += L % 10;

if (cube == 0)

zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)

L /= 10;

}

cout << endl;

}

return 0;

}

Ссылки

Рабочий код на Ideaone.

Тут можно посмотреть саму последовательность.

Related Images:

Ю2.18

01/11/2015 by Холодков Юрий

Задача.

Заданы координаты вершин тругольника [latex] ABC [/latex] на плоскости. Вывести их в порядке обхода по часовой стрелке (для проверки достаточно рассмотреть знаки внутренних углов).

Задача взята из задачника по программированию Юркина.

Тесты

Координаты вершин [latex] x, y [/latex] [latex] a, b [/latex] [latex] c, d [/latex]	Вывод по часовой стрелке [latex] x, y [/latex] [latex] a, b [/latex] [latex] c, d [/latex]
-2 -2 4 1 -1 4	( 4 1) (-2 -2 ) ( -1 4)
-2 -2 -1 4 4 1	( 4 1) (-2 -2 ) ( -1 4)
4 1 -2 -2 -1 4	( 4 1) (-2 -2 ) ( -1 4)
4 1 -1 4 -2 -2	( 4 1) (-2 -2 ) ( -1 4)
-1 4 -2 -2 4 1	( 4 1) (-2 -2 ) ( -1 4)
-1 4 4 1 -2 -2	( 4 1) (-2 -2 ) ( -1 4)

Код

#include <iostream>
using namespace std;

int main() {
    int x, y, a, b, c, d;
    cin >> x >> y >> a >> b >> c >> d;
    if ( x >= c && x >= a && c >= a && d >= b && y <= d ) {
        cout << " ( " << x << " " << y << " ) " <<
        "( " << a << " " << b << " )" << " ( " << c << " " << d << " ) ";}
    else if ( x >= c && x >=a && a >= c && b >= d && y <= b ){
        cout << " ( " << x << " " << y << " ) " <<
        "( " << c << " " << d << " )" << " ( " << a << " " << b << " ) ";}
    else if ( c >= a && c >= x && x >= a && y >= b && d <= y ){
        cout << " ( " << c << " " << d << " ) " <<
        "( " << a << " " << b << " )" << " ( " << x << " " << y << " ) ";}
    else if ( c >= x && c >= a && a >= x && b >= y && d <= b){
        cout << " ( " << c << " " << d << " ) " <<
        "( " << x << " " << y << " )" << " ( " << a << " " << b << " ) ";}
    else if ( a >= c && a >= x && c >= x && d >= y && b <= d ){
        cout << " ( " << a << " " << b << " ) " <<
        "( " << x << " " << y << " )" << " ( " << c << " " << d << " ) ";}
    else if ( a >= c && a >= x && x >= c && y >= d && b <= y){
        cout << " ( " << a << " " << b << " ) " <<
        "( " << c << " " << d << " )" << " ( " << x << " " << y << " ) ";}
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, y, a, b, c, d;

cin >> x >> y >> a >> b >> c >> d;

if ( x >= c && x >= a && c >= a && d >= b && y <= d ) {

cout << " ( " << x << " " << y << " ) " <<

"( " << a << " " << b << " )" << " ( " << c << " " << d << " ) ";}

else if ( x >= c && x >=a && a >= c && b >= d && y <= b ){

cout << " ( " << x << " " << y << " ) " <<

"( " << c << " " << d << " )" << " ( " << a << " " << b << " ) ";}

else if ( c >= a && c >= x && x >= a && y >= b && d <= y ){

cout << " ( " << c << " " << d << " ) " <<

"( " << a << " " << b << " )" << " ( " << x << " " << y << " ) ";}

else if ( c >= x && c >= a && a >= x && b >= y && d <= b){

cout << " ( " << c << " " << d << " ) " <<

"( " << x << " " << y << " )" << " ( " << a << " " << b << " ) ";}

else if ( a >= c && a >= x && c >= x && d >= y && b <= d ){

cout << " ( " << a << " " << b << " ) " <<

"( " << x << " " << y << " )" << " ( " << c << " " << d << " ) ";}

else if ( a >= c && a >= x && x >= c && y >= d && b <= y){

cout << " ( " << a << " " << b << " ) " <<

"( " << c << " " << d << " )" << " ( " << x << " " << y << " ) ";}

return 0;

}

Решение

В задаче не указано, с какой вершины следует выводить координаты, так что за точку отсчета берется крайняя правая. Для этого находим большее из [latex] x, c, d [/latex]. Из оставшихся двух точек находим нижнюю, находя меньшее значение по оси ординат. Поскольку значения по оси ординат могут совпадать, проверяем также значение по оси абсцисс и выбираем меньшее из двух.

Так как точек три и у каждой есть два варианта расположения относительно двух других, в программе используется 6 if-ов.

Решение на ideone.

Related Images:

Mif 14

30/10/2015 by Андрей Яроцкий

Задача:

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

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

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

[latex]A(x_1;y_1),B(x_2;y_2),C(x_3;y_3),D(x_4;y_4)[/latex].

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

Расположение отрезков [latex]AB[/latex] и [latex]CD[/latex] относительно друг друга:

Прямые в разных плоскостях,
Прямые параллельны,
Отрезки находятся на одной прямой но не совпадают,
Отрезки совпадают,
Отрезки пересекаются,
Отрезки не пересекаются;

Тесты:

№	Координаты [latex]A(x_1;y_1)B(x_2;y_2)C(x_3;y_3)D(x_4;y_4)[/latex]	Расположение отрезков
1	1 1 1 2 2 2 0 5 0 2 6 -1	Прямые в разных плоскостях
2	1 1 1 -1 -1 -1 0 0 -1 2 2 1	Прямые параллельны
3	1 1 0 2 2 1 4 4 3 5 5 4	Отрезки находятся на одной прямой но не совпадают
4	0 0 0 3 3 6 2 2 4 5 5 10	Отрезки совпадают
5	0 0 0 1 1 1 0 1 1 0 -1 -1	Отрезки пересекаются
6	0 0 1 1 1 1 5 -2 5 4 -1 4	Отрезки не пересекаются
7	1 0 0 1 1 0 0 0 1 1 0 1	Прямые в разных плоскостях
8	1 1 0 1 1 5 2 4 -1 2 4 1	Прямые параллельны
9	1 1 0 2 1 0 5 1 0 6 1 0	Отрезки находятся на одной прямой но не совпадают

10	-1 -1 -1 1 1 1 0 0 0 2 2 2	Отрезки совпадают
11	1 1 4 2 2 4 2 1 4 1 2 4	Отрезки пересекаются
12	1 0 3 1 3 3 2 2 3 4 4 3	Отрезки не пересекаются

#include <iostream>
using namespace std;
 
double Mixed(double ax, double ay, double az, double bx, double by, double bz, double cx, double cy, double cz){
    return (ax*by*cz)+(ay*bz*cx)+(az*bx*cy)-(az*by*cx)-(ay*bx*cz)-(ax*bz*cy);   // Формула смешаного произведения, если = 0, то одна плоскость
}
 
bool Collinear(double ax, double bx, double ay, double by, double az, double bz){
    return ((ax/bx) == (ay/by) && (ay/by) == (az/bz)) ? true:false;   // Коллинеарность
}
 
bool VectorEquation(double x, double x0, double y, double y0, double z, double z0, double Vx, double Vy, double Vz){
    return  (x - x0)/Vx == (y - y0)/Vy && (y - y0)/Vy == (z - z0)/Vz ? true:false;   // уравнение прямой в пространстве 
}
 
double Min(double X1, double X2){
    return X1 < X2 ? X1:X2;
}
double Max(double X1, double X2){
    return X1 > X2 ? X1:X2;
}
bool CollinearforPerp(double ax, double ay, double az, double bx, double by, double bz){    // Условие коллинеарности при bx,by,bz=0
    return ((ay*bz-az*by == 0) && (az*bx-ax*by == 0) && (ax*by-ay*bx == 0)) ? true:false;
}
 
 
int main() {
    double Xa, Ya, Za, Xb, Yb, Zb, Xc, Yc, Zc, Xd, Yd, Zd;    // Координаты концов отрезков
    cin >> Xa >> Ya >> Za >> Xb >> Yb >> Zb >> Xc >> Yc >> Zc >> Xd >> Yd >> Zd;
    double VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz; //Координаты векторов
 
    VectorABx = Xb-Xa;
    VectorABy = Yb-Ya;
    VectorABz = Zb-Za;
 
    VectorCDx = Xd-Xc; 
    VectorCDy = Yd-Yc;
    VectorCDz = Zd-Zc;
 
    VectorACx = Xc-Xa;
    VectorACy = Yc-Ya;
    VectorACz = Zc-Za;

    if (Mixed(VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz) == 0){ // Смешанное произведение
        if(Xc == Xd || Yc == Yd || Zc == Zd){                                                                           // Частный случай, если прямая перпендикулярна какой-либо оси
            if(CollinearforPerp(VectorABx,VectorABy,VectorABz,VectorCDx,VectorCDy,VectorCDz)){                                     // Прямые Коллинеарны
                if((Xc == Xd && Xa != Xc) || (Yc == Yd && Ya != Yc) || (Zc == Zd && Za != Zd)){                         // Условие параллельности 
                    cout << "Прямые параллельны" << endl; 
                }
                else{
                    if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){
                        if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){
                            if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){
                                cout << "Отрезки совпадают" << endl;                                    // Пресечение отрезков
                            }
                            else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;
                        }
                        else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;
                    }
                    else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;                   
                }                           
            }
            else{
                if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){
                        if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){
                            if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){
                                cout << "Отрезки пересекаются" << endl;
                            }
                            else cout << "Отрезки не пересекаются" << endl;
                        }
                        else cout << "Отрезки не пересекаются" << endl;
                    }
                    else cout << "Отрезки не пересекаются" << endl;
            }
            return 0;
        }
        else{
            if (Collinear(VectorABx, VectorCDx, VectorABy, VectorCDy, VectorABz, VectorCDz)){                    // Прямые коллинеарны
                if(VectorEquation(Xa, Xc, Ya, Yc, Za, Zc, VectorCDx, VectorCDy, VectorCDz)){             // Совпадение прямых
                    if((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd)){ // Совпадение отрезков
                        cout<< "Отрезки совпадают" << endl;
                    }
                    else{ 
                        cout << "Отрезки на одной прямой но не совпадают" << endl;
                    }
                }
                else{
                    cout << "Прямые параллельны" << endl;
                }
            }
            else{
                if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) || (Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){
                    cout << "Отрезки пересекаются" << endl;
                }
                else cout << "Отрезки не пересекаются" << endl;
                }
        }
    }
    else{
        cout << "Прямые в разных плоскостях" << endl;
    }
    return 0;
}

100

101

102

103

#include <iostream>

using namespace std;

double Mixed(double ax, double ay, double az, double bx, double by, double bz, double cx, double cy, double cz){

return (ax*by*cz)+(ay*bz*cx)+(az*bx*cy)-(az*by*cx)-(ay*bx*cz)-(ax*bz*cy); // Формула смешаного произведения, если = 0, то одна плоскость

}

bool Collinear(double ax, double bx, double ay, double by, double az, double bz){

return ((ax/bx) == (ay/by) && (ay/by) == (az/bz)) ? true:false; // Коллинеарность

}

bool VectorEquation(double x, double x0, double y, double y0, double z, double z0, double Vx, double Vy, double Vz){

return (x - x0)/Vx == (y - y0)/Vy && (y - y0)/Vy == (z - z0)/Vz ? true:false; // уравнение прямой в пространстве

}

double Min(double X1, double X2){

return X1 < X2 ? X1:X2;

}

double Max(double X1, double X2){

return X1 > X2 ? X1:X2;

}

bool CollinearforPerp(double ax, double ay, double az, double bx, double by, double bz){ // Условие коллинеарности при bx,by,bz=0

return ((ay*bz-az*by == 0) && (az*bx-ax*by == 0) && (ax*by-ay*bx == 0)) ? true:false;

}

int main() {

double Xa, Ya, Za, Xb, Yb, Zb, Xc, Yc, Zc, Xd, Yd, Zd; // Координаты концов отрезков

cin >> Xa >> Ya >> Za >> Xb >> Yb >> Zb >> Xc >> Yc >> Zc >> Xd >> Yd >> Zd;

double VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz; //Координаты векторов

VectorABx = Xb-Xa;

VectorABy = Yb-Ya;

VectorABz = Zb-Za;

VectorCDx = Xd-Xc;

VectorCDy = Yd-Yc;

VectorCDz = Zd-Zc;

VectorACx = Xc-Xa;

VectorACy = Yc-Ya;

VectorACz = Zc-Za;

if (Mixed(VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz) == 0){ // Смешанное произведение

if(Xc == Xd || Yc == Yd || Zc == Zd){ // Частный случай, если прямая перпендикулярна какой-либо оси

if(CollinearforPerp(VectorABx,VectorABy,VectorABz,VectorCDx,VectorCDy,VectorCDz)){ // Прямые Коллинеарны

if((Xc == Xd && Xa != Xc) || (Yc == Yd && Ya != Yc) || (Zc == Zd && Za != Zd)){ // Условие параллельности

cout << "Прямые параллельны" << endl;

}

else{

if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){

if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){

if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){

cout << "Отрезки совпадают" << endl; // Пресечение отрезков

}

else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;

}

else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;

}

else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;

}

else{

if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){

if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){

if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){

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

}

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

}

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

}

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

}

return 0;

}

else{

if (Collinear(VectorABx, VectorCDx, VectorABy, VectorCDy, VectorABz, VectorCDz)){ // Прямые коллинеарны

if(VectorEquation(Xa, Xc, Ya, Yc, Za, Zc, VectorCDx, VectorCDy, VectorCDz)){ // Совпадение прямых

if((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd)){ // Совпадение отрезков

cout<< "Отрезки совпадают" << endl;

}

else{

cout << "Отрезки на одной прямой но не совпадают" << endl;

}

else{

cout << "Прямые параллельны" << endl;

}

else{

if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) || (Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){

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

}

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

}

else{

cout << "Прямые в разных плоскостях" << endl;

}

return 0;

}

Алгоритм решения:

Для решения задачи нам понадобятся следующие функции:

1.[latex]Mixed[/latex] — функция возвращающая значение смешанного произведения векторов

(Основная формула [latex]a_xb_yc_z+a_yb_zc_x+a_zb_xc_y-a_zb_yc_x-a_yb_xc_z-a_xb_zc_y [/latex])

2.[latex]Collinear[/latex] — функция принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.

(Основная формула [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex] )

3.[latex]VectorEquation[/latex] — Функция принимающая координаты двух точек принадлежащих разным прямым и координаты направляющего вектора, и возвращающая логическое значение true, если они принадлежат одной прямой, и false в противном случае.

(Основная формула [latex]\frac{x — x_0}{V_x} =\frac{y — y_0}{V_y} = \frac{z — z_0}{V_z}[/latex] )

4.[latex]Min[/latex] — возвращает минимум двух чисел.

5.[latex]Max[/latex] – возвращает максимум двух чисел.

6.[latex]CollinearforPerp[/latex] — функция принимающая координаты векторов, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае. Используется в случае для формулы коллинеарности [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex] при [latex]b_x=0[/latex] , [latex]b_y=0[/latex] или [latex]b_z=0[/latex].

(Основная формула [latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex] )

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

Далее проверяем является ли какой либо вектор перпендикулярным какой-либо оси. Это необходимо так как в таком случае координаты вектора [latex] \vec{CD}[/latex] равны нулю, что недопустимо при делении функций на координаты данного вектора.

В случае если какой либо вектор перпендикулярный какой-либо оси, проверяем их коллинеарность по формуле [latex]CollinearforPerp[/latex]:

[latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex]

Если векторы коллинеарны то они параллельны в том случае, если координата вектора перпендикулярного некой оси не равна координате другого вектора той же оси [latex](X_c=X_d and X_a \neq X_c)[/latex] [latex]||[/latex] [latex](Y_c=Y_d and Y_a \neq Y_c)[/latex] [latex]||[/latex] [latex](Z_c=Z_d and Z_a \neq Z_c)[/latex] . В противном случае прямые совпадают. Отрезки также совпадают если одна из координат одного отрезка находится между большим и меньшем значением координат другого отрезка, для всех осей:

[latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_c and Max(X_a,X-b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

В противном случае отрезки находятся на одной прямой но не совпадают.

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

[latex](Min(X_a,X_b)[/latex][latex]\le[/latex][latex]X_c and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

Если же ни один вектор не перпендикулярен ни одной оси, проверяем вектора на коллинеарность стандартным способом ([latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex])

Для коллинеарных векторов используем функцию VectorEquation которая возвращает логическое значение true, если точка одного отрезка принадлежит прямой другому, и false если векторы перпендикулярны. Проверка на совпадение отрезков проводиться аналогично первому случаю.

Когда вектора не коллинеарны, прямые пересекаются. Проверка на пересечение отрезков проводиться аналогично первому случаю.

Ссылка на код программы

Ссылка на условие задачи

Related Images:

Mif 15

26/10/2015 by Женя Максимова

Задача. Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин в четырехмерном пространстве.

Тесты

(1)

№	[latex]A_0[/latex]	[latex]A_1 [/latex]	[latex]A_2[/latex]	[latex]A_3[/latex]	[latex]B_0[/latex]	[latex]B_1[/latex]	[latex]B_2[/latex]	[latex]B_3[/latex]
1	1	0	0	0	2	0	0	0
2	1	0	0	0	3	0	0	0
3	-1	1	0	6	-2	-1	1	6
4	1	1	1	1	2	2	2	2
5	1	1	1	2	8	5	7	10
6	1	1	0	0	1	0	1	1
7	3	4	7	8	9	5	6	2
8	1	2	2	3	1	4	8	9

(2)

№	[latex]C_0[/latex]	[latex]C_1[/latex]	[latex]C_2[/latex]	[latex]C_3[/latex]	[latex]D_0[/latex]	[latex]D_1[/latex]	[latex]D_2[/latex]	[latex]D_3[/latex]	[latex]r[/latex]
1	1	1	0	0	2	1	0	0	1.000000
2	2	4	0	0	2	4	3	0	4.000000
3	-1	-1	0	6	2	1	1	6	1.154701
4	-9	-9	-9	-9	-5	-5	-5	-5	12.000000
5	8	0	0	0	2	1	1	1	1.414214
6	2	3	2	0	1	4	9	1	3.000000
7	7	4	11	15	15	5	12	9	9.000000
8	5	7	2	23	4	8	8	21	13.000000

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

#include "stdio.h"
#include <cmath>

double dot(double * u, double * v);
double abs(double * u);
double min(double a, double b, double c, double d);
void prod(double k, double * u, double * v);
void diff(double * a, double * b, double * c);
void summ(double * a, double * b, double * c);
bool in(double s);
bool in(double s, double t);
double sd(double s, double t);
double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];
double u[4],v[4],w0[4];

double InterSegmentDistance4d()
//input: four 4d points P0, P1, Q0, Q1
// output: r = minimal distance between lines segments P0P1 and Q0Q1
    {
        double r = 0;
        //calculation of three vectors
        //u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0
        diff(P1, P0, u);  diff(Q1, Q0, v);  diff(Q0, P0, w0);
        //calculation of supporting scalar variables
        //a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v
        double  a, b, c, d, e;
        a = dot(u,u);  // a=u^2;
        b = dot(u,v);         
        c = dot(v,v);  // c=v^2;
        d = dot(u,w0);
        e = dot(v,w0);
        //calculation of main determinant
        // D = b^2 - a*c
        double D = b*b - a*c;
        if (D == 0) //lines are parallel
            {
                double t0=-e/c; 
                double t1=-e/c; 
                double s0 = (-e+b)/c ; 
                double s1= (e-c)*b/(c*a);
                if (in(t0) || in(t1) || in(s0) || in(s1))
                    {
                        double wq[4];
                        prod(e/c,v,  wq);  //projection w0 on line q
                        double wd[4];
                         diff(w0,wq,  wd);
                          r = abs(wd);
                           return r ; //r = |w0 - wq|
                    }
                //else minimal distance between segments equals minimal distance between ends of segments
                        r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));
                         return r;   
            }
        // else lines are not parallel
            {
                //calculation of determinants
                double D1 = b*e - c*d,  D2 = a*e - b*d;
                //calculation of parameters for minimal segment between lines
                double sc = D1/D, tc = D2/D;
                if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines
                    {
                        return r = sd(sc,tc); // r = |wc|
                    }
                //else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]
                    {
                        double t1 = 0,   s1=_(d/a);
                        double t2 = _(-2*e/c), s2=0;
                        double t3 = 1,   s3=_(2*(b+d)/a);
                        double t4 = _(2*(b+e)/c), s4=0;
                         return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4)); 
                    }
            }
    }

int main()
    {
        scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);
        scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);
        scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);
        scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);
         printf("%lf\n", InterSegmentDistance4d());
          return 0;
    }

double dot(double * u, double * v)//scalar production of two vectors
    {
        return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];
    }

double abs(double * u)//length of vector
    {
        return sqrt(dot(u,u));
    }

double min(double a, double b, double c, double d)//minimal from four values
    {
        double m = a;
        if(m>b) m = b;
         if(m>c) m = c;
          if(m>d) m = d;
           return m;
    }

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)
    {
        c[0]=a[0]-b[0];
        c[1]=a[1]-b[1];
        c[2]=a[2]-b[2];
        c[3]=a[3]-b[3];
    }

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)
    {
        c[0]=a[0]+b[0];
        c[1]=a[1]+b[1];
        c[2]=a[2]+b[2];
        c[3]=a[3]+b[3];
    }

void prod(double k, double * u, double * v)//production of number and vector
    {
        v[0] = k * u[0];
        v[1] = k * u[1];
        v[2] = k * u[2];
        v[3] = k * u[3];
    }

bool in(double s)//checking if the vatue is in [0,1]
    {
        return 0 <= s && s <= 1 ;
    }

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]
    {
        return  in(t) && in(s);
    }

double sd(double s, double t)//distance between two points defined by two parameters s and t
    {
        double Pc[4], Qc[4], W[4];
        prod(s,u, Pc);
        prod(t,v, Qc);
         summ(Pc,P0, Pc);
         summ(Qc,Q0, Qc);
          diff(Qc, Pc, W);
           return  abs(W);
    }

double _(double s)//restrict a value s on the interval [0,1]
    {
        double s1 = s;
        if(s > 1)s1 = 1;
        if(s < 0)s1 = 0;
         return s1;
    }

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include "stdio.h"

#include <cmath>

double dot(double * u, double * v);

double abs(double * u);

double min(double a, double b, double c, double d);

void prod(double k, double * u, double * v);

void diff(double * a, double * b, double * c);

void summ(double * a, double * b, double * c);

bool in(double s);

bool in(double s, double t);

double sd(double s, double t);

double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];

double u[4],v[4],w0[4];

double InterSegmentDistance4d()

//input: four 4d points P0, P1, Q0, Q1

// output: r = minimal distance between lines segments P0P1 and Q0Q1

{

double r = 0;

//calculation of three vectors

//u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0

diff(P1, P0, u); diff(Q1, Q0, v); diff(Q0, P0, w0);

//calculation of supporting scalar variables

//a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v

double a, b, c, d, e;

a = dot(u,u); // a=u^2;

b = dot(u,v);

c = dot(v,v); // c=v^2;

d = dot(u,w0);

e = dot(v,w0);

//calculation of main determinant

// D = b^2 - a*c

double D = b*b - a*c;

if (D == 0) //lines are parallel

{

double t0=-e/c;

double t1=-e/c;

double s0 = (-e+b)/c ;

double s1= (e-c)*b/(c*a);

if (in(t0) || in(t1) || in(s0) || in(s1))

{

double wq[4];

prod(e/c,v, wq); //projection w0 on line q

double wd[4];

diff(w0,wq, wd);

r = abs(wd);

return r ; //r = |w0 - wq|

}

//else minimal distance between segments equals minimal distance between ends of segments

r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));

return r;

}

// else lines are not parallel

{

//calculation of determinants

double D1 = b*e - c*d, D2 = a*e - b*d;

//calculation of parameters for minimal segment between lines

double sc = D1/D, tc = D2/D;

if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines

{

return r = sd(sc,tc); // r = |wc|

}

//else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]

{

double t1 = 0, s1=_(d/a);

double t2 = _(-2*e/c), s2=0;

double t3 = 1, s3=_(2*(b+d)/a);

double t4 = _(2*(b+e)/c), s4=0;

return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4));

}

int main()

{

scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);

scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);

scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);

scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);

printf("%lf\n", InterSegmentDistance4d());

return 0;

}

double dot(double * u, double * v)//scalar production of two vectors

{

return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];

}

double abs(double * u)//length of vector

{

return sqrt(dot(u,u));

}

double min(double a, double b, double c, double d)//minimal from four values

{

double m = a;

if(m>b) m = b;

if(m>c) m = c;

if(m>d) m = d;

return m;

}

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)

{

c[0]=a[0]-b[0];

c[1]=a[1]-b[1];

c[2]=a[2]-b[2];

c[3]=a[3]-b[3];

}

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)

{

c[0]=a[0]+b[0];

c[1]=a[1]+b[1];

c[2]=a[2]+b[2];

c[3]=a[3]+b[3];

}

void prod(double k, double * u, double * v)//production of number and vector

{

v[0] = k * u[0];

v[1] = k * u[1];

v[2] = k * u[2];

v[3] = k * u[3];

}

bool in(double s)//checking if the vatue is in [0,1]

{

return 0 <= s && s <= 1 ;

}

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]

{

return in(t) && in(s);

}

double sd(double s, double t)//distance between two points defined by two parameters s and t

{

double Pc[4], Qc[4], W[4];

prod(s,u, Pc);

prod(t,v, Qc);

summ(Pc,P0, Pc);

summ(Qc,Q0, Qc);

diff(Qc, Pc, W);

return abs(W);

}

double _(double s)//restrict a value s on the interval [0,1]

{

double s1 = s;

if(s > 1)s1 = 1;

if(s < 0)s1 = 0;

return s1;

}

Алгоритм и его обоснование

Расстояние между отрезками в четырехмерном пространстве находится по-разному, в зависимости от взаимного расположения этих отрезков. Тут мы можем выделить два основных случая:

Отрезки лежат на параллельных прямых или на одной прямой.
Отрезки лежат на пересекающихся либо на скрещивающихся прямых.

Чтобы выяснить, с каким случаем мы имеем дело, рассмотрим общую картину взаимного расположения отрезков и опишем ее математически:

По условию нам заданы 4 точки: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] — концы двух отрезков. Для удобства представления уравнений и точек, связанных с ними, обозначим их [latex]P_0[/latex], [latex]P_1[/latex], [latex]Q_0[/latex] и [latex]Q_1[/latex] соответственно. Через эти пары точек мы можем провести 2 прямые [latex]p[/latex] и [latex]q[/latex], параметрические уравнения которых имеют вид:

[latex]

\begin{matrix}
\vec p = P_0 + \vec u \cdot s \\
\vec q = Q_0 + \vec v \cdot t
\end{matrix}

[/latex],

где векторы:

[latex]

\begin{matrix}

\vec u = P_1 — P_0\\

\vec v = Q_1 — Q_0

\end{matrix}

[/latex],

а [latex]s[/latex] и [latex]t[/latex] — параметры. При [latex]s=0[/latex] или [latex] t=0[/latex] мы получаем начальную точку соответствующего отрезка, а при [latex]s=1[/latex] или [latex]t=1[/latex] — конечную. При произвольном значении параметра мы получаем произвольную точку на прямой.

Рассмотрим вектор [latex]\vec w = Q — P[/latex] , соединяющий 2 произвольные точки на этих прямых. Легко показать, что вектор [latex]\vec w[/latex] соединяет 2 ближайшие точки [latex]Q_c[/latex] и [latex]P_c[/latex] при условии:

[latex]\vec w \perp p[/latex] и [latex]\vec w \perp q[/latex].

Этому условию соответствует система из двух уравнений:

[latex] \begin{cases}
\vec u \cdot \vec w = 0\\
\vec v \cdot \vec w = 0
\end{cases}

[/latex]

Распишем ее для [latex]\vec w = Q_0 — P_0 + \vec v \cdot t — \vec u \cdot s = \vec w_0 + \vec v \cdot t — \vec u \cdot s[/latex] :
[latex]

\begin{cases}
\vec u \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0\\
\vec v \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0
\end{cases}

[/latex]

Введем вспомогательные скалярные переменные:
[latex]

\begin{matrix}

a&=&\vec u \cdot \vec u\\
b&=&\vec u \cdot \vec v\\
c&=&\vec v \cdot \vec v\\
d&=&\vec u \cdot \vec w_0\\
e&=&\vec v \cdot \vec w_0

\end{matrix}

[/latex]

Теперь наша система будет выглядеть так:

[latex]

\begin{cases}
d — a \cdot s + b \cdot t = 0 \\
e — b \cdot s + c \cdot t = 0
\end{cases}
[/latex]

Перепишем систему в удобном для нас виде:

[latex] \begin{cases}
a \cdot s — b \cdot t = d \\
b \cdot s — c \cdot t = e
\end{cases}
[/latex]

Решение этой системы мы можем получить, например, методом Крамера.

Главный определитель системы: [latex]D = b^2 — a \cdot c[/latex]

Два вспомогательных определителя:
[latex] \begin{matrix}
D_1 = b \cdot e — c \cdot d\\
D_2 = a \cdot e — b \cdot d\\
\end{matrix}
[/latex] Если [latex]D \neq 0[/latex], то существует единственное решение:

[latex]

\begin{cases}
s_c = \frac{D_1}{D} \\
t_c = \frac{D_2}{D}
\end{cases}
[/latex]

Если же мы получаем [latex]D = 0[/latex], легко показать, что отрезки параллельны. То есть мы имеем дело со случаем 1.

Тогда:

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

Найдем проекцию точки [latex]P_0[/latex] на линию [latex]q[/latex]. Для этого сначала найдем вектор, который является проекцией вектора [latex]\vec w_0[/latex] на линию [latex]q[/latex].

[latex]\vec w_q=(\vec w_0 \cdot \vec v) \cdot \frac{\vec v}{v^2}[/latex].
Конец полученного вектора находится в точке [latex]Q_0[/latex], а начало в новой точке [latex]P_{0q}=Q_0-\vec w_q[/latex]. Соединим точки [latex]P_0[/latex] и [latex]P_{0q}[/latex] вектором [latex]\vec w_p = P_{0q} — P_0[/latex]. Длина полученного вектора и будет искомым расстоянием: [latex]r = \left| P_0 P_{0q} \right|[/latex].

Для проверки условия а) необходимо получить проекции остальных исходных точек на отрезки:
[latex] \begin{matrix}
P_{1q} = P_{0q} + \vec u\\
Q_{0p} = P_0 + \vec w_q\\
Q_{1p} = Q_{0p} + \vec v
\end{matrix}
[/latex]

Если точка [latex]P_{0q}[/latex] лежит на прямой [latex]q[/latex], задаваемой уравнением:
[latex]\vec q = Q_0 + \vec v \cdot t[/latex],
то определить, принадлежит ли точка [latex]P_{0q}[/latex] отрезку [latex]Q_0 Q_1[/latex] можно, решив уравнение:
[latex]P_{0q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q + \vec v \cdot t[/latex].
Домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение: [latex] 0 = e + c \cdot t[/latex], отсюда [latex]t = \frac{-e}{c}[/latex].

Если [latex]t \in \left[0,1\right][/latex], то точка [latex]P_{0q}[/latex] лежит на отрезке [latex]Q_0 Q_1[/latex]. Если же нет, переходим к аналогичной проверке следующих точек:

[latex]P_{1q}:[/latex] [latex]P_{1q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q — \vec u + \vec v \cdot t[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение:

[latex] 0 = e — b + c \cdot t[/latex],
отсюда [latex]t = \frac{-e+b}{c}[/latex].
[latex]Q_{0p}:[/latex] [latex]Q_{0p} = P_0 + \vec u \cdot s[/latex].
[latex]0 =-\vec w_q + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} + a \cdot s[/latex],
отсюда [latex]s = \frac{e \cdot b}{c \cdot a}[/latex].
[latex]Q_{1p}:[/latex] [latex]Q_{1p} = P_0 + \vec u \cdot s[/latex].
[latex] 0 = -\vec w_q — \vec v + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} — b + a \cdot s[/latex],
отсюда [latex]s = \frac{(e — c) \cdot b}{c \cdot a}[/latex].
б) В противном случае, расстояние между отрезками равняется минимальному расстоянию между их концами. Здесь задача предельно упрощается. Мы находим длины отрезков, попарно соединяющих 4 исходные точки, и выбираем наименьший из них.

Если же исходные отрезки лежат на пересекающихся либо на скрещивающихся прямых, мы также рассматриваем 2 случая:

а) Оба конца кратчайшего отрезка, соединяющего прямые, лежат на соответствующих исходных отрезках:
[latex]P_c \in P_0 P_1[/latex] и [latex]Q_c \in Q_0 Q_1[/latex].

В этом случае пара параметров [latex](s_c, \; t_c)[/latex] принадлежит области: [latex](s,t):\left[0,1\right]\times \left[0,1\right].[/latex]

То есть, решение тривиально: ответом будет дина вектора [latex]\vec w_c[/latex]

б) Хотя бы один из концов кратчайшего отрезка, соединяющего прямые, не лежит на исходном отрезке, то есть:
[latex]P_c \not\in P_0 P_1[/latex] или [latex]Q_c \not\in Q_0 Q_1[/latex],
что соответствует значениям параметров [latex]s_c \not\in \left[0,1\right][/latex] или [latex]t_c \not\in \left[0,1\right][/latex].

В этом случае минимальное расстояние между отрезками определяется на границе области: [latex](s,t):\left[0,1\right]\times \left[0,1\right][/latex] (см. рисунок ниже):

Здесь решением является длина кратчайшего отрезка.

Длину отрезка, соединяющего 2 прямые, можно оценивать по квадрату длины вектора [latex]\vec v[/latex]: [latex]w^2=(\vec w)^2=(\vec w_0 — \vec u \cdot s + \vec v \cdot t)^2[/latex].

В частности, минимум [latex]w^2[/latex] достигается в точке [latex](s_c,t_c)[/latex].
Однако в случае б) мы должны найти минимум расстояния на границе нашей области, то есть решить задачу нахождения минимума при ограничениях (решить задачу условной минимизации). В нашем случае ограничения имеют очень простой вид — оси координат, и две линии, параллельные им. Поэтому мы можем решить на четырех границах 4 упрощенные задачи минимизации, а затем выбрать наименьшее решение.

Замечание: В пространстве параметров функция [latex]w^2(s,t)[/latex] представляет из себя эллиптический параболоид. Однако для простоты мы выше изобразили его линии уровня в виде окружностей. Типичный вид эллиптического параболоида и его линий уровня представлен на рисунках ниже:

Рассмотрим поочередно все 4 ограничения и решим задачу для них:

(1) Пусть [latex]t=t_1=0[/latex].

Тогда: [latex]{w^2\mid_{t_1=0}} = (\vec w_0-\vec u \cdot s_1)^2[/latex].

Для определения экстремума приравняем производную к нулю:[latex] \begin{array}{r}
\frac{d}{ds_1}{(\vec w_0-\vec u \cdot s_1)^2}=0\\
2 \cdot (\vec w_0-\vec u \cdot s_1) \cdot (- \vec u)=0\\
-d +a \cdot s_1=0\\
s_1=\frac{d}{a}
\end{array}
[/latex]

Легко показать, что при [latex]s_1>1[/latex] мы должны присвоить ему значение [latex]s_1=1[/latex], а если [latex]s<0[/latex] — значение [latex]s_1=0[/latex], так как мы не должны выходить за границы исходных отрезков.

Подставим полученное значение [latex]s[/latex] в уравнение прямой [latex]p[/latex] для точки [latex]P_c[/latex]:[latex]P_c = P_0 + \vec u \cdot s.[/latex]

А точка [latex]Q_c[/latex] совпадает с точкой [latex]Q_0[/latex]. Тогда первый минимум равен: [latex]r_1 = Q_0 P_c[/latex].

Аналогично найдем три остальных минимума [latex]r_2, r_3, r_4[/latex], приравняв [latex]s[/latex] к нулю, а затем [latex]t[/latex] и [latex]s[/latex] к единице. Наименьший из них и есть искомое расстояние [latex]r[/latex].

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

Related Images:

Mif 17.8

10/10/2015 by Катя Писова

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

Решение:

Фигура, изображенная на рисунке, ограничена двумя дугами окружностей с центрами в начале координат. Для того, чтобы точка принадлежала ей необходимо, чтобы ее ордината была больше либо равнялась двум, а также, чтобы выполнялись такие неравенства: [latex]{x}^{2}+{y}^{2}>=16[/latex] и [latex]{x}^{2}+{y}^{2}<=36[/latex], где [latex]16[/latex] и [latex]36[/latex] — радиусы двух окружностей, возведенные в квадрат по формуле.

Код:

#include <iostream>
using namespace std;
 
int main() {
    double x,y;
    cin>>x>>y;
    cout<<( y >= 2 && x*x + y*y >= 16 && x*x + y*y <= 36 ? "YES" : "NO");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin>>x>>y;

cout<<( y >= 2 && x*x + y*y >= 16 && x*x + y*y <= 36 ? "YES" : "NO");

return 0;

}

Тесты:

x	y	Результат
0	0	NO
-1	4	YES
6	-2	NO
2.5	3	NO

Тут можно посмотреть решение задачи на ideone.com

Related Images:

Mif3

09/10/2015 by Кирилл Демиденко

Задача

Даны действительные числа [latex] x [/latex], [latex] y [/latex], [latex] z [/latex]. Получить [latex]min\left ( x,y,z \right )[/latex] .

Тесты

Входные данные:	4 3 2	0 2 1	0 -1 4	2 3 4
Выходные данные:	2	0	-1	2

#include <iostream>
using namespace std;
int main()
{
    double x, y, z; 
    cin >> x >> y >> z;
    double min = x; // x- минимальное 
    if (y < min) { // сравниваем y с x
        min = y; // и если y меньше, то выводим y
    }
    if (z < min) { // сравниваем z с x
        min = z; // если z меньше, то выводим z
    }
    cout << min << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

double x, y, z;

cin >> x >> y >> z;

double min = x; // x- минимальное

if (y < min) { // сравниваем y с x

min = y; // и если y меньше, то выводим y

}

if (z < min) { // сравниваем z с x

min = z; // если z меньше, то выводим z

}

cout << min << endl;

return 0;

}

Описание решения:

Предположим, что [latex] x [/latex] минимальное из трёх чисел, и путем сравнения с [latex]y[/latex] выясняем, какое из этих двух чисел минимальное. Если [latex]x[/latex] остается минимальным, то сравниваем его с [latex]z[/latex], а если [latex]y[/latex] окажется меньше, то его сравниваем с [latex]z[/latex] и после выводим минимальное из трех чисел на экран.

Related Images:

Mif 17.13

07/10/2015 by Таня Корнилова

Задача №17.13

Условие

Принадлежит ли точка (х;у) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты

Входные данные (точка K)	Выходные данные
(3;4)	no
(1;1)	yes
(1;4)	yes
(3;0)	yes
(0;6)	no
(-13; -3)	no
(-4.5; -3)	yes

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

#include <iostream>
#include <stdio.h>
using namespace std;

struct point { double x, y; };

double g(struct point a, struct point b, struct point k){
	return (k.x - a.x) * (b.y - a.y) - (k.y - a.y) * (b.x - a.x);
} // определяем местоположение точки K относительно прямой АВ

bool f(struct point a, struct point b, struct point c, struct point k){
	return g(a, b, c) * g(a, b, k) >= 0;
} // определяем, лежит ли точка С в одной полуплоскости с точкой К

int main() {
	struct point a { 1, 4 }, b { 5, -4 }, c { -5, -3 };
	double x, y;
	struct point k { k.x, k.y };
	cin >> k.x >> k.y;
	cout << ((f(a,b,c,k) && f(b,c,a,k) && f(c,a,b,k)) ? "yes" : "no");
	return 0;

}

#include <iostream>

#include <stdio.h>

using namespace std;

struct point { double x, y; };

double g(struct point a, struct point b, struct point k){

return (k.x - a.x) * (b.y - a.y) - (k.y - a.y) * (b.x - a.x);

} // определяем местоположение точки K относительно прямой АВ

bool f(struct point a, struct point b, struct point c, struct point k){

return g(a, b, c) * g(a, b, k) >= 0;

} // определяем, лежит ли точка С в одной полуплоскости с точкой К

int main() {

struct point a { 1, 4 }, b { 5, -4 }, c { -5, -3 };

double x, y;

struct point k { k.x, k.y };

cin >> k.x >> k.y;

cout << ((f(a,b,c,k) && f(b,c,a,k) && f(c,a,b,k)) ? "yes" : "no");

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

[latex](x — x_A)(y_B — y_A) — (y — y_A)(x_B — x_A) = 0[/latex] — уравнение прямой, проходящей через точки [latex]A[/latex] и [latex]B[/latex]. Тогда для любой точки [latex](x; y)[/latex] можно определить её местоположение относительно прямой [latex]AB[/latex]. Если левая часть неравенства будет равно 0, то точка лежит на прямой. Прямая [latex]AB[/latex] разбивает плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения, а точки из другой полуплоскости — отрицательные. Тогда, объединением условий местоположения точки [latex](x; y)[/latex] и местоположения точек [latex]C, A, B[/latex] относительно прямых [latex]AB[/latex], [latex]BC[/latex], [latex]AC[/latex] соответственно, мы сможем определить местоположение данной точки относительно треугольника.

По рисунку видно, что [latex]A(1;4), B(5, -4), C(-5, -3)[/latex]. Тогда, определяем положение точки [latex]K[/latex] относительно каждой прямой и точки не лежащей на данной прямой треугольника [latex]ABC[/latex].

Related Images:

Ю2.16

07/10/2015 by Кондратюк Настя

Задача

Задача взята из задачника А.Юркина

Кратные пары

Среди заданных целых чисел [latex]k, l, m[/latex] найти пары кратных.

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

Целые числа [latex]k, l, m[/latex].
[latex] \left | k,l,m \right |< 2\cdot 10^{9} [/latex]

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

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

Тесты

	Входные данные	Выходные данные
1.	1 2 3	1 2 1 3
2.	0 2 4	2 4
3.	1 2 6	1 2 1 6 2 6
4.	5 5 2	5 5
5.	0 0 3
6.	2 5 3
7.	-10 5 2

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

#include <iostream>
using namespace std;

int main() {
	int k,l,m;
	cin >> k >> l >> m;
	if (k>0){
		if (l>0){
			if (m>0){
				if ((k%m==0)||(m%k==0)) 
					cout << k << " " << m << endl;
				if ((k%l==0)||(l%k==0)) 
					cout << k << " " << l << endl;
				if ((l%m==0)||(m%l==0)) 
					cout << l << " " << m << endl;
			}
			else if ((k%l==0)||(l%k==0)) 
					cout << k << " " << l << endl;
		}
		else if ((m>0) && ((m%k==0)||(k%m==0))) 
				cout << m << " " << k << endl;
	}
	else if ((l>0) && (m>0) && ((l%m==0)||(m%l==0))) 
			cout << l << " " << m << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int k,l,m;

cin >> k >> l >> m;

if (k>0){

if (l>0){

if (m>0){

if ((k%m==0)||(m%k==0))

cout << k << " " << m << endl;

if ((k%l==0)||(l%k==0))

cout << k << " " << l << endl;

if ((l%m==0)||(m%l==0))

cout << l << " " << m << endl;

}

else if ((k%l==0)||(l%k==0))

cout << k << " " << l << endl;

}

else if ((m>0) && ((m%k==0)||(k%m==0)))

cout << m << " " << k << endl;

}

else if ((l>0) && (m>0) && ((l%m==0)||(m%l==0)))

cout << l << " " << m << endl;

return 0;

}

ideone.com

Решение

Хотя свойство делимости определено на всём множестве целых чисел, обычно рассматривается лишь делимость натуральных чисел.

Кратное натурального числа [latex]b[/latex] — это натуральное число [latex]a[/latex], которое делится на [latex]b[/latex] нацело. Наименьшим кратным данного числа является само это число.

Related Images:

А57г. Функция

07/10/2015 by Александр Коломеец

Постановка задачи

Дано действительное число [latex]a[/latex]. Вычислить [latex]f(a)[/latex], если
[latex]f(x) = \begin{cases}0, & x \le 0;\\x^2 — x, & 0 < x \le 1;\\x^2 — \sin(\pi \cdot x^2), & x > 1 \end{cases}[/latex]

Алгоритм решения

Находим промежуток, которому принадлежит [latex]a[/latex]. Если [latex]a \in (-\infty;0][/latex], то [latex]f(a) = 0[/latex], если [latex]a \in (0;1][/latex], то [latex]f(a) = a^2 — a[/latex], в остальных случаях [latex]f(a) = a^2 — \sin(\pi \cdot a ^ 2)[/latex].

График функции:

Тесты

Входные данные	Выходные данные
0	0
1	0
2	4

Реализация

ideone: ссылка

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

int main() {
	double a;
	cin >> a;
	cout << (a <= 0 ? 0 : a <= 1 ? a * a - 1 : a * a - sin(M_PI * a * a)) << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a;

cin >> a;

cout << (a <= 0 ? 0 : a <= 1 ? a * a - 1 : a * a - sin(M_PI * a * a)) << endl;

return 0;

}

Related Images:

A39

07/10/2015 by Настя Панько

Даны два действительных числа. Вывести первое число, если оно больше второго, и оба числа, если это не так.

Код

#include <iostream>
using namespace std;

int main() {
    double x, y;
    cin >> x >> y;
    if ( x > y ){
        cout << x;
    }
    else 
        cout << x << y;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y;

cin >> x >> y;

if ( x > y ){

cout << x;

}

else

cout << x << y;

return 0;

}

Тесты

Входные данные		Выходные данные
x	y
3	2	3
10	5	10
30	20	30
50	30	50

Решение

Пусть даны два действительных числа x, y. Для ввода x и y используем тип double для действительных чисел. Задаем условие, если первое число больше второго, используя оператор if. Выводим первое число x.

Вводим else, если это не так. Выводим оба числа.

Код задачи

Ideone.com

Related Images:

Mif 17.14

07/10/2015 by Холодков Юрий

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex] y[/latex]) фигуре на рисунке? Вариант 14. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Задача взята здесь.

Тесты

[latex]x[/latex]	[latex] y[/latex]	Ответ
-2	4	Принадлежит
4	8	Не принадлежит
-7	9	Не принадлежит
0	0	Не принадлежит
0	1	Принадлежит
4	1	Принадлежит
-7	1	Принадлежит

Код

#include <iostream>
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    if ( (y <= 7) && (y >= 1) && (y - 2*x <= 15) && (y + 2*x <= 15))
    {cout << "Принадлежит";}
        else {cout << "Не принадлежит";}
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, y;

cin >> x >> y;

if ( (y <= 7) && (y >= 1) && (y - 2*x <= 15) && (y + 2*x <= 15))

{cout << "Принадлежит";}

else {cout << "Не принадлежит";}

return 0;

}

Решение

Каждая из сторон тарпеции делит плоскость на 2 части. Сторона имеет вид [latex]y = k*x + b[/latex]. Путем подстановки были найдены коефициенты [latex] k [/latex] и [latex] b [/latex]. Точка может лежать либо ниже, либо выше, либо на стороне. Если [latex]y — k*x <= b[/latex], точка лежит на или ниже стороны. Основы трапеции представлены в виде [latex] y =1 [/latex] и [latex] y = 7 [/latex].

Ссылка на ideone.com

Related Images:

Mif 7. Тип треугольника

07/10/2015 by Александр Коломеец

Тип треугольника.

Постановка задачи

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex], задающие длины сторон некоторого треугольника. Будет ли треугольник остроугольным, тупоугольным или прямоугольным? Какой из трёх случаев самый маловероятный?

Алгоритм решения

По теореме косинусов
[latex]a^2 = b^2 + c^2 — 2 \cdot b \cdot c \cdot \cos\alpha[/latex],
где [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] — стороны треугольника, а [latex]\alpha[/latex] — угол между [latex]a[/latex] и [latex]b[/latex], тогда
[latex]\alpha = \arccos\frac{b^2 + c^2 — a^2}{2 \cdot b \cdot c}[/latex],
[latex]\beta = \arccos\frac{c^2 + a^2 — b^2}{2 \cdot a \cdot c}[/latex],
[latex]\gamma = \arccos\frac{a^2 + b^2 — c^2}{2 \cdot a \cdot b}[/latex],
где [latex]\alpha[/latex], [latex]\beta[/latex], [latex]\gamma[/latex] — углы треугольника.
Если самый большой угол больше [latex]\frac{\pi}{2}[/latex], то треугольник тупоугольный, если самый большой угол равен [latex]\frac{\pi}{2}[/latex], то треугольник прямоугольный, если самый большой угол меньше [latex]\frac{\pi}{2}[/latex], то треугольник остроугольный. Так как треугольник является прямоугольным только в том случае, когда самый большой угол равен [latex]\frac{\pi}{2}[/latex], этот случай является самым маловероятным.

Тесты

Входные данные			Выходные данные
[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	Выходные данные
2	2	3	Тупоугольный
3	4	5	Прямоугольный
1	1	1	Остроугольный

Реализация

ideone: ссылка

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

int main() {
	double a, b, c;
	cin >> a >> b >> c;
	double angle0 = acos((b * b + c * c - a * a) / (2 * b * c));
	double angle1 = acos((c * c + a * a - b * b) / (2 * a * c));
	double angle2 = acos((a * a + b * b - c * c) / (2 * a * b));
	double maxAngle = angle0 > angle1 ? (angle0 > angle2 ? angle0 : angle2) : (angle1 > angle2 ? angle1 : angle2);
	if(maxAngle > M_PI / 2) {
		cout << "Тупоугольный";
	} else if(maxAngle == M_PI / 2) {
		cout << "Прямоугольный";
	} else {
		cout << "Остроугольный";
	}
	cout << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, b, c;

cin >> a >> b >> c;

double angle0 = acos((b * b + c * c - a * a) / (2 * b * c));

double angle1 = acos((c * c + a * a - b * b) / (2 * a * c));

double angle2 = acos((a * a + b * b - c * c) / (2 * a * b));

double maxAngle = angle0 > angle1 ? (angle0 > angle2 ? angle0 : angle2) : (angle1 > angle2 ? angle1 : angle2);

if(maxAngle > M_PI / 2) {

cout << "Тупоугольный";

} else if(maxAngle == M_PI / 2) {

cout << "Прямоугольный";

} else {

cout << "Остроугольный";

}

cout << endl;

return 0;

}

Related Images:

Mif 8

07/10/2015 by Настя Ивасенко

Задача

Условие взято отсюда

Четырёхугольник [latex]ABCD[/latex] задан на плоскости целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Из характеристик указать наиболее частную.

Тесты

[latex]a_1[/latex] [latex]a_2[/latex]	[latex]b_1[/latex] [latex]b_2[/latex]	[latex]c_1[/latex][latex]c_2[/latex]	[latex]d_1[/latex] [latex]d_2[/latex]	Ответ
0 0	1 0	1 1	0 1	квадрат
0 -3	2 0	0 3	-2 0	ромб
0 0	4 0	4 1	1 4	прямоугольник
0 0	10 0	12 4	2 4	пaраллелограмм
0 0	2 0	1 1	0 1	трапеция
0 0	0 2	1 1	1 0	трапеция
-4 -5	-15 7	5 8	6 -7	произвольный
0 0	1 0	10 20	-5 7	произвольный

Код

#include <iostream>
using namespace std;
 
int main() {
	int a1, a2, b1, b2, c1, c2, d1, d2;
	double  AB, BC, CD, DA, AC, BD, A, B, C, D;
	cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;
	AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени
	BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));
	CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));
	DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));
	AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени
	BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));
	if(AB==CD && BC==DA) {
		if (AB==BC){
			if(AC==BD){
				cout << "квадрат";
			}
			else {
				cout << "ромб";
			}
		}
		else 
		if (AC==BD){
			cout<< "прямоугольник";
		}
		else{
			cout << "параллелограмм";
		}
	}
	else 
	if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){
		cout << "трапеция";
	}
	else {
		cout << "произвольный";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int a1, a2, b1, b2, c1, c2, d1, d2;

double AB, BC, CD, DA, AC, BD, A, B, C, D;

cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;

AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени

BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));

CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));

DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));

AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени

BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));

if(AB==CD && BC==DA) {

if (AB==BC){

if(AC==BD){

cout << "квадрат";

}

else {

cout << "ромб";

}

else

if (AC==BD){

cout<< "прямоугольник";

}

else{

cout << "параллелограмм";

}

else

if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){

cout << "трапеция";

}

else {

cout << "произвольный";

}

return 0;

}

Решение

Для начала стоит найти длины всех сторон:

[latex]AB^{2}=((a1-b1)^{2}+(a2-b2)^{2})[/latex]. (аналогично для остальных сторон)

Затем можно найти длины диагоналей четырёхугольника

[latex]AC^{2}=((a1-c1)^{2}+(a2-c2)^{2})[/latex]. (аналогично для [latex]BD[/latex]).

Через условие задаем равность противоположных сторон [latex]AB=CD[/latex] и [latex]BC=DA[/latex]:

У ромба смежные стороны равны, но если у ромба диагонали равны, то это квадрат;
Если четырёхугольник не является квадратом, но диагонали равны, то это прямоугольник;
В противном случае — параллелограмм.

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

Код на ideone