e-olymp 8649. Емблема (Emblem)

20/06/2019 by Blyshchyk

Умова

До проведення $N$-ї ярмарки «Мікротехнології у макропрограмуванні» дизайнери розробили емблему, у якій на квадрат розміром $N \times N$ дм «ставився зверху» квадрат розміром $\left(N-1\right) \times \left(N-1\right)$ дм і так далі. Зверху був квадрат $1 \times 1.$ В цілому організаторам емблема сподобалася, але вони забажали «прикрасити» її золотистою стрічкою, яка йшла б від лівого нижнього кута до правого верхнього, потім по верхньому краю і спускалася до правого нижнього кута (див. малюнок). У найближчому магазині можна було купити стрічку за ціною $Р$ грн. за дм, але відпускалися стрічки тільки з цілою кількістю дм. У той же час магазин пропонував знижку $10\%$, якщо покупка коштувала не менше $100$ грн. і $15\%$ при покупці від $1000$ грн. Скільки щонайменше доведеться заплатити за цю «прикрасу»? Нагадаємо, що на декартовій площині довжина відрізку між точками $\left(x_{1};y_{1}\right)$ та $\left(x_{2};y_{2}\right)$ обчислюється за формулою: $d=\sqrt{\left(\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2} \right)}.$

Вхідні дані:

Програма вводить два натуральних числа $N$ – номер ярмарки та $P$ -ціна стрічки у гривнях за дм $\left(1 \leqslant N \leqslant 100\right).$

Вихідні дані:

Ціна стрічки у копійках (щоб не працювати з дробовими числами).

Тести:

Вхідні дані	Вихідні дані
2 13	9360
5 10	28800
100 1	858670
1 5	2000
12 3	42660

Рішення:

#include 
#include 
using namespace std;

int main() {
    long long N, P;
    cin >> N >> P;
    double h, l, d, lenta, price;
    h = (1+N)*N*0.5;
    l = 0.5 + N*0.5;
    d = sqrt(h*h + l*l);
    lenta = ceil(d + d + 1);
    price = lenta * P;
    if (price >= 1000) {
        price *= 85;
    }
    else if (price >= 100) {
        price *= 90;
    }
    else {
        price *= 100;
    }
    if (ceil(100./P) > lenta and price > 90*ceil(100./P)*P){
        price = 90*ceil(100./P)*P;
    }
    else if (ceil(1000./P) > lenta and price > 85*ceil(1000./P)*P) {
        price = 85*ceil(1000./P)*P;
    }
    cout << price;
}

#include

using namespace std;

int main() {

long long N, P;

cin >> N >> P;

double h, l, d, lenta, price;

h = (1+N)*N*0.5;

l = 0.5 + N*0.5;

d = sqrt(h*h + l*l);

lenta = ceil(d + d + 1);

price = lenta * P;

if (price >= 1000) {

price *= 85;

}

else if (price >= 100) {

price *= 90;

}

else {

price *= 100;

}

if (ceil(100./P) > lenta and price > 90*ceil(100./P)*P){

price = 90*ceil(100./P)*P;

}

else if (ceil(1000./P) > lenta and price > 85*ceil(1000./P)*P) {

price = 85*ceil(1000./P)*P;

}

cout << price;

}

Пояснення: Спочатку необхідно знайти довжину діагоналі, для цього, умовно ми можемо продовжити саму верхню пряму в праву і ліву сторону до того моменту поки її довжина не стане не менш ніж $N$ дм, а потім починаючи з лівого нижнього кута куба $N \times N$ провести перпендикуляр до цієї прямої. Так у нас вийде прямокутний трикутник, в якому h (знаходимо за формулою $n$-перших членів арифметичної прогресії $S_{n} = \frac{a_{1}+a_{n}}{2} \cdot n$) та l — катети, тоді за теоремою Піфагора можемо знайти діагональ d. Далі знаходимо довжину стрічки і її ціну з огляду на знижки. Також необхідно зробити перевірку, чи буде вигідніше придбати стрічку на таку кількість грошей, яке буде відповідати умовам знижки.

Related Images:

e-olymp 1509. Раздел королевства.

25/12/2018 by Виктор Иванов

Задача

Король страны Геометрии в заботах. У него есть три сына, которые постоянно ссорятся. Король применял разные методы примерения, но все напрасно. И это его очень беспокоило.

«А что если разделить королевство?» подумал король. Он пригласил советников и описал свой план. Король открыл карту.

Королевство имеет форму треугольника с вершинами [latex]A, B, C[/latex]. Король провел линию от [latex]B[/latex] к [latex]E[/latex] ([latex]E[/latex] — произвольная точка на отрезке [latex]AC[/latex]) и линию от [latex]C[/latex] к [latex]F [/latex]([latex]F[/latex] — произвольная точка на отрезке [latex]AB[/latex]). Пересечение [latex]BE[/latex] и [latex]CF[/latex] обозначено через [latex]X[/latex].

Теперь образовалось четыре части — [latex]a[/latex] (треугольник [latex]BFX[/latex]), [latex]b[/latex] (треугольник [latex]BCX[/latex]), [latex]c[/latex] (треугольник [latex]CEX[/latex]) и [latex]d[/latex] (четырехугольник [latex]AEXF[/latex]). Король решил отдать области[latex] a[/latex], [latex]b[/latex], [latex]c[/latex] трем сыновьям. А область [latex]d[/latex] станет новым королевством.

Вы — главный советник. Король сообщает Вам значения [latex]a, b, c[/latex]. Вам необходимо найти значение [latex]d[/latex]. Если его найти невозможно, то сообщить об этом.

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

Состоит из не более чем [latex]1000[/latex] тестов. Каждый тест содержит три неотрицательных действительных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] (разделенных пробелом). Входные данные заканчиваются тестом у которого [latex]a = -1[/latex] и он не обрабатывается.

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

Для каждого теста вывести его номер, начиная с [latex]1[/latex]. В следующей строке вывести [latex]d[/latex] (величина области королевства после раздела) округленное до [latex]4[/latex] десятичных знаков или ‘Poor King!’ (без кавычек) если значение [latex]d[/latex] определить невозможно. Формат выходных данных показан в примере.

Тесты

№	Входные данные	Выходные данные
1	1 2 1	Set 1: 2.0000
2	2 4 2	Set 2: 4.0000
3	1 3 3	Set 3: 5.0000
4	-1 0 0

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

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

int main () {
    double a, b, c, d, d1, d2;
    int l = 0;
    while (cin >> a >> b >> c && a!= -1.0) {
        d1 = a * c / b;
        l++;
        if (b > d1) {
            d2 = (c + d1) * (a + d1) / (b - d1);
            cout << fixed << setprecision(4) << "Set" << " " << l << ':' << endl;
            cout << d1 + d2<< endl;
        }
        else cout << "Set" << " " << l << ':' << endl << "Poor King!" << endl;
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main () {

double a, b, c, d, d1, d2;

int l = 0;

while (cin >> a >> b >> c && a!= -1.0) {

d1 = a * c / b;

l++;

if (b > d1) {

d2 = (c + d1) * (a + d1) / (b - d1);

cout << fixed << setprecision(4) << "Set" << " " << l << ':' << endl;

cout << d1 + d2<< endl;

}

else cout << "Set" << " " << l << ':' << endl << "Poor King!" << endl;

}

return 0;

}

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

Для решения задачи соединим точки [latex]F[/latex] и [latex]E[/latex] линией. Получили два треугольника: [latex]d1[/latex] и [latex]d2[/latex]. Искомую площадь [latex]d[/latex] будем искать как сумму площадей [latex]d1[/latex] и [latex]d2[/latex]. Треугольники [latex]BFO[/latex] и [latex]EFO[/latex] имеют общее основание [latex]FO[/latex]. Следовательно их площади [latex]d1[/latex] и [latex]a[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]FO[/latex]. Аналогично треугольники [latex]BCO[/latex] и [latex]ECO[/latex] имеют общее основание [latex]OF[/latex]. Значит их площади [latex]c[/latex] и [latex]b[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]CO[/latex]. То есть $\frac{d_1}{a}=\frac{c}{b}$. Отсюда $d_1=\frac{ac}{b}$. Теперь рассмотрим треугольники [latex]CAF[/latex] и [latex]CBF[/latex] с основаниями [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]С[/latex] на прямую [latex]AB[/latex]. Следовательно площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Аналогично треугольники [latex]EAF[/latex] и [latex]EBF[/latex] имеют основания [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]E[/latex] на прямую [latex]AB[/latex]. Площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Тогда $$\frac{AF}{BF}=\frac{S_{\blacktriangle} CAF}{S\blacktriangle CBF}=\frac{c+d_1+d_2}{a+b}$$. $$\frac{AF}{BF}=\frac{S\blacktriangle EAF}{S\blacktriangle EBF}=\frac{d_2}{a+d_1}$$. Следовательно $\frac{c+d_1+d_2}{a+b}=\frac{d_2}{a+d_1}$. Поскольку [latex]d1[/latex] уже найдено, то имеем равенство с одним неизвестным [latex]d2[/latex] : $$d_2=\frac{(c+d_1)(a+d_1)}{b-d_1}$$. Если [latex]b \leqslant d1[/latex], то решения не существует.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

Related Images:

Proggy-Buggy 2018: Задача E. Треугольник или не треугольник?

04/12/2018 by Владислав Бебик

Задача

Баги считает треугольником любые три различные точки плоскости, соединенные отрезками. Даже написал диссертацию: «Треугольник или не треугольник? Вот в чём вопрос!», которая породила множество вопросов. Его очень утомили вопросы из разряда, «а это треугольник?». Если хотите, помогите Баги: напишите программу «Баги-бот», которая вместо Баги отвечала бы на вопрос, образуют ли три заданные точки треугольник.

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

Строка содержащая три пары целых чисел, координаты $x1$, $y1$, $x2$, $y2$, $x3$, $y3$ $(0\leq xi,yi\leq1000)$, разделенных пробелом.

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

Строка «$yes$» или «$no$» (без кавычек) — ответ программы «Баги-бот».

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 0 1 0 0 1	$yes$
2	1 1 1 2 1 3	$yes$
3	1 1 1 1 1 2	$no$

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

#include <iostream>
using namespace std;

int main() {
    int x1,y1,x2,y2,x3,y3;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
	if ((x1==x2 && y1==y2) || (x2==x3 && y2==y3) || (x3==x1 && y3==y1)) cout << "no";
	else cout << "yes";
	return 0;
}

#include <iostream>

using namespace std;

int main() {

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

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

if ((x1==x2 && y1==y2) || (x2==x3 && y2==y3) || (x3==x1 && y3==y1)) cout << "no";

else cout << "yes";

return 0;

}

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

В задаче главное внимательно прочитать условие. Если любые две заданные точки совпадают, то программа «Баги-бот» должна ответить no, иначе yes.

Ссылки

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

Related Images:

e-olymp 8372. Составить треугольник

28/09/2018 by Алина Гук

Задача взята с сайта e-olymp

Задача

По заданным длинам трех отрезков определить, можно ли из них составить невырожденный треугольник. Треугольник называется невырожденным, если его площадь больше 0.

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

Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.

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

Вывести YES если из отрезков можно составить невырожденный треугольник и NO в противном случае.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 6 7	YES
2	3 7 4	NO
3	16 24 32	YES
4	54 1 100	NO
5	1 1 1	YES

Код программы (Ветвление)

#include <iostream>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");

return 0;

}

Код программы (Линейные вычисления)

#include <iostream>
using namespace std;
 
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  bool condition = (a < b + c && b < a + c && c < a + b); 
  cout  << (char)(condition * 'Y' + !condition * 'N')
        << (char)(condition * 'E' + !condition * 'O')
        << (char)(condition * 'S' + !condition * ' ');
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

bool condition = (a < b + c && b < a + c && c < a + b);

cout << (char)(condition * 'Y' + !condition * 'N')

<< (char)(condition * 'E' + !condition * 'O')

<< (char)(condition * 'S' + !condition * ' ');

return 0;

}

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

Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}

Ссылки

Условие задачи на e-olymp

Код программы на ideone (Линейные вычисления)

Код программы на ideone (Ветвление)

Related Images:

e-olymp 47. Паркет из треугольников

24/06/2018 by Артем Чернобровкин

Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

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

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

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

Искомое количество шагов.

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
5	3 2 6 12	2

Код 1

#include <iostream>
using namespace std;

int main()
{
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    //создание динамического массива
    int*** arr;
    arr = new int**[vertSize];
    int count = 1;
    int z = 2;
    int apos[3];
    int bpos[3];
    for (int i = 0; i < vertSize; i++)
    {
        arr[i] = new int*[horSize];
        for (int j = 0; j < horSize; j++)
        {
            arr[i][j] = new int[z];
            for (int k = 0; k < 2; k++)
            {
                arr[i][j][k] = count;
                count++;
                // определяем позицию наших элементов в массиве
                if (arr[i][j][k] == firstNumber)
                {
                    apos[0] = i;
                    apos[1] = j;
                    apos[2] = k;
                }
                if (arr[i][j][k] == lastNumber)
                {
                    bpos[0] = i;
                    bpos[1] = j;
                    bpos[2] = k;
                }
            }
        }
    }
    int hor;
    int vert;
    // направление движения по вертикали
    vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);
    // направление движения по горизонтали
    hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);
    int stepCount = 0;
    int curCell[3];
    for (int i = 0; i < 3; i++)
        curCell[i] = apos[i];

    bool dir;
    if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)
        dir = false;
    else
        dir = true;
    while (1)
    {
        if (dir && vert != 0)
        {
            if (vert == -1)
            {
                if (curCell[2] == 0)
                    curCell[0]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[0]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        else if (!dir && hor != 0)
        {
            if (hor == -1)
            {
                if (curCell[2] == 0)
                    curCell[1]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[1]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        dir = !dir;

        if (curCell[0] == bpos[0])
            vert = 0;
        if (curCell[1] == bpos[1])
            hor = 0;

        if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])
        {
            curCell[2] = !((bool)curCell[2]);
            stepCount++;
        }

        bool end;
        for (int i = 0; i < 3; i++)
        {
            if (curCell[i] != bpos[i])
            {
                end = false;
                break;
            }
            end = true;
        }
        if (end)
            break;
    }
    cout << stepCount << endl;
    return 0;
}

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

#include <iostream>

using namespace std;

int main()

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

//создание динамического массива

int*** arr;

arr = new int**[vertSize];

int count = 1;

int z = 2;

int apos[3];

int bpos[3];

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

{

arr[i] = new int*[horSize];

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

{

arr[i][j] = new int[z];

for (int k = 0; k < 2; k++)

{

arr[i][j][k] = count;

count++;

// определяем позицию наших элементов в массиве

if (arr[i][j][k] == firstNumber)

{

apos[0] = i;

apos[1] = j;

apos[2] = k;

}

if (arr[i][j][k] == lastNumber)

{

bpos[0] = i;

bpos[1] = j;

bpos[2] = k;

}

int hor;

int vert;

// направление движения по вертикали

vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);

// направление движения по горизонтали

hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);

int stepCount = 0;

int curCell[3];

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

curCell[i] = apos[i];

bool dir;

if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)

dir = false;

else

dir = true;

while (1)

{

if (dir && vert != 0)

{

if (vert == -1)

{

if (curCell[2] == 0)

curCell[0]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[0]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else if (!dir && hor != 0)

{

if (hor == -1)

{

if (curCell[2] == 0)

curCell[1]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[1]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

dir = !dir;

if (curCell[0] == bpos[0])

vert = 0;

if (curCell[1] == bpos[1])

hor = 0;

if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])

{

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

bool end;

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

{

if (curCell[i] != bpos[i])

{

end = false;

break;

}

end = true;

}

if (end)

break;

}

cout << stepCount << endl;

return 0;

}

Код 2

#include <iostream>
using namespace std;
int main() {
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    if (firstNumber > lastNumber){
        swap(firstNumber, lastNumber);  
    } 
    //вычисление координат
    int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    int Search[2 * horSize];
    Search[firstNumberx - 1] = 0;
    int step = 1;
    for (int i = firstNumberx - 2; i >= 0; i--){
        Search[i] = step++;
        
    }
    step = 1;
    for (int i = firstNumberx; i < 2 * horSize; i++){
        Search[i] = step++;
    }
    //сравнение по у
    for (int j = firstNumbery; j < lastNumbery; j++) {
        for (int i = 1; i < 2 * horSize; i += 2) {
            Search[i - 1] = Search[i] + 1;
            Search[i] += 2;
            //определние значения на предпоследнем элементе
            if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                Search[i - 2] = Search[i];
            }
        }
    }
    cout << Search[lastNumberx - 1] << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

if (firstNumber > lastNumber){

swap(firstNumber, lastNumber);

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int Search[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

for (int i = firstNumberx; i < 2 * horSize; i++){

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

for (int i = 1; i < 2 * horSize; i += 2) {

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определние значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

cout << Search[lastNumberx - 1] << endl;

return 0;

}

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

Способ 1

Каждый элемент имеет три параметра:

Положение в строке
Положение в столбце
Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

Оба элемента расположены в одной строке строке
Оба элемента расположены в одном столбце
Оба элемента расположены на одной диагонали
Произвольное расположение

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

firstNumber = 7;
lastNumber = 14;

1 2	firstNumber = 7; lastNumber = 14;

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

(bool)curCell[2]

1	(bool)curCell[2]

Для более оптимальной работы были использованы тернарные операции. Они скрывают под собой условие, выполнение которого состоит из одной строки кода.

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

int V[2 * horSize];

1	int V[2 * horSize];

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

Search[firstNumberx - 1];

1	Search[firstNumberx - 1];

стояло количество шагов, совершенных в ходе решения.

Ссылки

Задача на e-olymp

Код задачи на ideone ( способ 1 )

Код задачи на ideone ( способ 2 )

Related Images:

e-olymp 143. Точка и треугольник

26/12/2017 by Александра Филистович

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

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

№	Входные данные	Выходные данные
1	2 6 -9 3 8 1 5 11	1
2	-13 10 -12 5 99 80 17 13	0
3	98 -50 -87 7 5 3 23 17	0
4	5 15 7 12 5 3 2 54	1
5	2 2 3 1 1 3 9 11	1

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

#include <iostream>
using namespace std;
 
int main() {
 double x0,x1,x2,x3,y0,y1,y2,y3;
 double z1,z2,z3;
 cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
 z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);
 z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);
 z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);
 if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";
 else cout<<"0";
 return 0;
}

#include <iostream>

using namespace std;

int main() {

double x0,x1,x2,x3,y0,y1,y2,y3;

double z1,z2,z3;

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

z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);

z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);

z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);

if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";

else cout<<"0";

return 0;

}

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

Related Images:

ML29. Площадь тетраэдра

25/09/2016 by Алла Марокко

Тетраэдр

Задача. Найти площадь полной поверхности тетраэдра три стороны которого образованы векторами [latex]\overrightarrow{a}=(a_x,a_y,a_z)[/latex], [latex] \overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z)[/latex].
Тесты:

№	Вход									Выход
№	[latex]a_x[/latex]	[latex]a_y[/latex]	[latex]a_z[/latex]	[latex]b_x[/latex]	[latex]b_y[/latex]	[latex]b_z[/latex]	[latex]c_x[/latex]	[latex]c_y[/latex]	[latex]c_z[/latex]	[latex]S[/latex]
1	-3	3	3	3	-3	3	3	3	-3	69.3607
2	-1	1	1	1	-1	1	1	1	-1	7.70674
3	-2	2	2	2	-2	2	2	2	-2	30.827
4	0	0	1	1	0	0	1	1	-1	2.07313

Код на C++:

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double ax, ay, az, bx, by, bz, cx, cy, cz;//обозначим переменные
    cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;//введём переменные
    double A1A2 = sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2
    double A1A3 = sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3
    double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3
    double sina =sqrt(1-cosa*cosa);//вычислим их синус
    double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности
    double A1A4 = sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4
    double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4
    double sinb =sqrt(1-cosb*cosb);//вычислим их синус
    double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности
    double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4
    double sinc =sqrt(1-cosc*cosc);//вычислим их синус
    double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности
    double A2A3 = sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3
    double A2A4 = sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4
    double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4
    double sind =sqrt(1-cosd*cosd);//вычислим их синус
    double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности
    double s = s1+s2+s3+s4;//найдём площадь полной поверхности
    cout << s ;//выведем её результат
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double ax, ay, az, bx, by, bz, cx, cy, cz;//обозначим переменные

cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;//введём переменные

double A1A2 = sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2

double A1A3 = sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3

double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3

double sina =sqrt(1-cosa*cosa);//вычислим их синус

double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности

double A1A4 = sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4

double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4

double sinb =sqrt(1-cosb*cosb);//вычислим их синус

double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности

double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4

double sinc =sqrt(1-cosc*cosc);//вычислим их синус

double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности

double A2A3 = sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3

double A2A4 = sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4

double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4

double sind =sqrt(1-cosd*cosd);//вычислим их синус

double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности

double s = s1+s2+s3+s4;//найдём площадь полной поверхности

cout << s ;//выведем её результат

return 0;

}

Код на Java:

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

class Main{
    public static void main (String[] args) throws java.lang.Exception{
                Scanner in = new Scanner(System.in);
                PrintWriter out = new PrintWriter(System.out);
                double ax = in.nextDouble();
                double ay = in.nextDouble();
                double az = in.nextDouble();
                double bx = in.nextDouble();
                double by = in.nextDouble();
                double bz = in.nextDouble();
                double cx = in.nextDouble();
                double cy = in.nextDouble();
                double cz = in.nextDouble();
                double A1A2 = Math.sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2
                double A1A3 = Math.sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3
                double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3
                double sina = Math.sqrt(1-cosa*cosa);//вычислим их синус
                double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности
                double A1A4 = Math.sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4
                double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4
                double sinb = Math.sqrt(1-cosb*cosb);//вычислим их синус
                double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности
                double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4
                double sinc = Math.sqrt(1-cosc*cosc);//вычислим их синус
                double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности
                double A2A3 = Math.sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3
                double A2A4 = Math.sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4
                double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4
                double sind = Math.sqrt(1-cosd*cosd);//вычислим их синус
                double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности
                double s = s1+s2+s3+s4;//найдём площадь полной поверхности
                System.out.println(s) ;//выведем её результат
        }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main{

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

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

double ax = in.nextDouble();

double ay = in.nextDouble();

double az = in.nextDouble();

double bx = in.nextDouble();

double by = in.nextDouble();

double bz = in.nextDouble();

double cx = in.nextDouble();

double cy = in.nextDouble();

double cz = in.nextDouble();

double A1A2 = Math.sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2

double A1A3 = Math.sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3

double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3

double sina = Math.sqrt(1-cosa*cosa);//вычислим их синус

double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности

double A1A4 = Math.sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4

double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4

double sinb = Math.sqrt(1-cosb*cosb);//вычислим их синус

double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности

double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4

double sinc = Math.sqrt(1-cosc*cosc);//вычислим их синус

double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности

double A2A3 = Math.sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3

double A2A4 = Math.sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4

double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4

double sind = Math.sqrt(1-cosd*cosd);//вычислим их синус

double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности

double s = s1+s2+s3+s4;//найдём площадь полной поверхности

System.out.println(s) ;//выведем её результат

}

Решение:
Координаты векторов находим по формуле:
[latex] \overrightarrow{A_2A_4}=(c_x-a_x,c_y-a_y,c_z-a_z) [/latex] здесь [latex] a_x, a_y, a_z[/latex] — координаты точки [latex]A_2[/latex]; [latex]c_x, c_y, c_z[/latex] — координаты точки [latex]A_4[/latex];
Таким же образом находим остальные координаты векторов.
Модули векторов (длина ребер пирамиды)
Длина вектора [latex]\overrightarrow{a}(a_x;a_y;a_z)[/latex] выражается через его координаты формулой:
[latex] \left| \overrightarrow{A_1A_2} \right| =\sqrt { ({ a_x) }^{ 2 }+({ a_y) }^{ 2 }+({ a_z) }^{ 2 } } [/latex];
Таким же способом находим другие модули векторов.
Площадь грани можно найти по формуле:
[latex] s_1=\frac { 1 }{ 2 } \vec{A_1} \times \vec{A_2} \sin \angle{A_2A_3} [/latex] где
[latex] \sin \angle{ A_2A_3 =\sqrt { 1-{ (\cos \angle{ A_2A_3) } }^{ 2 } } } [/latex] Так же будем находить и другие.
Найдем угол между ребрами [latex] A_1A_2(a_x;a_y;a_z) [/latex] и [latex] A_1A_3(b_x;b_y;b_z) [/latex]:
[latex] \cos \angle{ A_2A_3 =\frac { a_x b_x+a_y b_y+a_z b_z }{ \left| A_2A_3 \right| } } [/latex] Так мы найдём и другие 3 площади граней.
Площадь полной поверхности.
[latex] s=s_1+s_2+s_3+s_4. [/latex]

Ссылки:

Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .
Онлайн калькулятор .

Related Images:

ML38. Максимальный размер прямоугольника, вырезанного из круга

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

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

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

Единственное число — диаметр окружности.

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

Два числа — длины сторон прямоугольника.

Тесты.

№	Входные данные	Выходные данные
	[latex]d[/latex]	[latex]a[/latex]	[latex]b[/latex]
1	0	0	0
2	1	0.850651	0.525731
3	2	1.7013	1.05146
4	21	17.8638	11.0404
5	0.32	0.272208	0.168234
6	1.7	1.44611	0.893743
7	134	113.981	70.448

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double a, b, f, d;
    cin >> d;
    f = (sqrt(5) + 1) / 2;
    b = d / sqrt (1 + f * f);
    a = b * f;
    cout << a << ' ' << b;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, b, f, d;

cin >> d;

f = (sqrt(5) + 1) / 2;

b = d / sqrt (1 + f * f);

a = b * f;

cout << a << ' ' << b;

return 0;

}

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

import java.util.*;
import java.math.*;
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        double f = (Math.sqrt(5)+1)/2;
        double d = in.nextDouble();
        double b = d / Math.sqrt(1 + f * f);
        double a = b * f;
        System.out.print(a + " " + b);
    }
}

import java.util.*;

import java.math.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double f = (Math.sqrt(5)+1)/2;

double d = in.nextDouble();

double b = d / Math.sqrt(1 + f * f);

double a = b * f;

System.out.print(a + " " + b);

}

Решение.

Прямоугольник будет иметь наибольший размер в случае, когда его вершины лежат на окружности. Тогда, очевидно, диаметр окружности будет диагональю данного прямоугольника. Согласно условию, длины его сторон образуют золотую пропорцию. Это означает, что [latex]\frac { a }{ b } =\phi [/latex], где [latex]a[/latex] — длина большей стороны прямоугольника, [latex]b[/latex] — длина его меньшей стороны, а [latex]\phi=\frac { 1+\sqrt { 5 } }{ 2 } [/latex]. Отсюда [latex]a=b\cdot \phi[/latex]. По теореме Пифагора, [latex]{ a }^{ 2 }+{ b }^{ 2 }={ d }^{ 2 }[/latex]. Путём подстановки из предыдущего выражения и простых алгебраических преобразований получим формулу для вычисления длины меньшей стороны: [latex]b=d\cdot \sqrt { \frac { 1 }{ { \phi }^{ 2 }+1 } } [/latex].
Сначала для удобства находим значение [latex]\phi[/latex], затем — по указанным формулам длины сторон прямоугольника.

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

Related Images:

ML26. Площадь треугольника

22/09/2016 by Даниил Юдин

Задача.

Найти площадь треугольника по заданным координатам его вершин [latex] A(x_a,y_a,z_a )[/latex], [latex]B(x_b,y_b,z_b)[/latex] и [latex]C(x_c,y_c,z_c)[/latex].

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

Координаты вершин треугольника [latex]ABC[/latex]

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

Площадь [latex]S[/latex] треугольника [latex]ABC[/latex]

Тесты

Входные данные									Выходные данные
[latex]x_a [/latex]	[latex]y_a [/latex]	[latex]z_a [/latex]	[latex]x_b [/latex]	[latex]y_b [/latex]	[latex]z_b [/latex]	[latex]x_c [/latex]	[latex]y_c [/latex]	[latex]z_c [/latex]	[latex]S [/latex]
-2	1	2	3	-3	4	1	0	9	19.7864
-3	13	-5	6	11	12	4	8	18	50.5618
-6	0	4	5	1	3	-3	-1	-4	43.307
-6	-2.3	-8.2	1.9	-7.8	0.2	-8.5	3.4	-8.9	28.0909

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

#include <iostream>
#include <cmath>
using namespace std;
//функция высчитывает расстояние между двумя координатами, координаты передаются в функцию при вызове
double side(double ax,double bx,double ay,double by,double az,double bz){
    return sqrt((bx-ax)*(bx-ax)+(by-ay)*(by-ay)+(bz-az)*(bz-az));
}
int main() {
    double ax,ay,az,bx,by,bz,cx,cy,cz;
    cin>>ax>>ay>>az>>bx>>by>>bz>>cx>>cy>>cz;
    double a=side(bx,ax,by,ay,bz,az);
    double b=side(cx,ax,cy,ay,cz,az);
    double c=side(bx,cx,by,cy,bz,cz);
    double p=(a+b+c)/2;
    double s=sqrt(p*(p-a)*(p-b)*(p-c));
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

//функция высчитывает расстояние между двумя координатами, координаты передаются в функцию при вызове

double side(double ax,double bx,double ay,double by,double az,double bz){

return sqrt((bx-ax)*(bx-ax)+(by-ay)*(by-ay)+(bz-az)*(bz-az));

}

int main() {

double ax,ay,az,bx,by,bz,cx,cy,cz;

cin>>ax>>ay>>az>>bx>>by>>bz>>cx>>cy>>cz;

double a=side(bx,ax,by,ay,bz,az);

double b=side(cx,ax,cy,ay,cz,az);

double c=side(bx,cx,by,cy,bz,cz);

double p=(a+b+c)/2;

double s=sqrt(p*(p-a)*(p-b)*(p-c));

cout<<s;

return 0;

}

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

Используя известные нам координаты вершин треугольника и формулу вычисления расстояния между двумя точками в пространстве [latex]AB=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}[/latex] можно найти длины сторон треугольника [latex]ABC[/latex]. Для нахождения площади используем Формулу Герона[latex]AB=\sqrt{p*(p-a)*(p-b)*(p-c)}[/latex] перед этим находим полупериметр [latex]p[/latex] по формуле [latex]p=\frac{a+b+c}{2}[/latex] подставляем значение и выводим конечный результат.

Ссылки

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

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:

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 17.15

01/10/2015 by Кудымовская Вика

Задача Mif17.15

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

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

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

В одной строке задано два числа – координаты точки latex[/latex].

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

Вывести: «Принадлежит» или «Не принадлежит»(без кавычек).

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

Тестирование

№	Входные данные	Выходные данные
1.	1.5 7	Не принадлежит
2.	3 4	Не принадлежит
3.	2 -3.6	Принадлежит
4.	5 0	Принадлежит
5.	0 1	Не принадлежит
6.	0 -4	Не принадлежит
7.	3 3	Принадлежит
8.	2 3	Принадлежит

Реализация

#include <iostream>
using namespace std;
 
int main () {
    double x, y, k, m, n;
    int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника
    cin >> x >> y; //координаты произвольной точки
    k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);
    m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);
    n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);
    cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main () {

double x, y, k, m, n;

int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника

cin >> x >> y; //координаты произвольной точки

k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);

m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);

n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);

cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");

return 0;

}

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

Пусть на плоскости дан треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]C(x_3, y_3)[/latex]. А [latex]D(x, y)[/latex] — произвольная точка на координатной плоскости. Положим, [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] — векторы.

Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
Если векторы заданы своими координатами [latex]a(x_1, y_1), b(x_2, y_2)[/latex], то их косое произведение [latex][a,b]=x_1\cdot y_2 — x_2\cdot y_1[/latex]. Пользуясь данной формулой, запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]D(x, y)[/latex]: [latex]k=x_1y_2 — x_2y_1 — x_1y + xy_1 + x_2y — xy_2=(x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex].
Далее запишем косое произведение векторов [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex]: [latex]m=x_2y_3 — x_3y_2 — x_2y + xy_2 + x_3y — xy_3=(x_2 -x)\cdot (y_ 3- y_2) — (x_3 — x_2)\cdot (y_2 — y)[/latex].
Запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] : [latex]n=x_1y_3 — x_3y_1 — x_1y + xy_1 + x_3y — xy_3=(x_3 — x)\cdot (y_1 — y_3) — (x_1 — x_3)\cdot (y_3 — y)[/latex].
Если [latex]k \leq 0 [/latex] и [latex]m \leq 0[/latex] и [latex]n \leq 0[/latex] или [latex]k \geq 0[/latex] и [latex]m \geq 0[/latex] и [latex]n \geq 0[/latex], то делаем вывод: точка принадлежит треугольнику.
Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

Ознакомиться с теоретическим материалом можно здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

Mif 17.1

30/09/2015 by Аня Шохина

Задача. Принадлежит ли точка [latex]\left(x;y \right)[/latex] фигуре на рисунке?

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

Два числа [latex] x[/latex], [latex]y[/latex] — координаты точки.

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

Слово «YES», если точка принадлежит треугольнику и «NO» , если не принадлежит.

Тесты

[latex]x[/latex]	[latex]y [/latex]	Результат
4	-2	NO
2	1	YES
0	3	YES
5	0	NO
0	-1	NO

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
	double x, y;
	cin>>x>>y;
	if ((abs(x)+y<=4) && (y>=0)){
		cout<<"YES";
	}
	else cout<<"NO";
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x, y;

cin>>x>>y;

if ((abs(x)+y<=4) && (y>=0)){

cout<<"YES";

}

else cout<<"NO";

return 0;

}

Код программы на ideone.com

Решение

Точка будет принадлежать треугольнику только при таких [latex]x[/latex] и [latex]y[/latex], что сумма их модулей не превышает 4. При выполнении условия выводим на экран: «YES». В противном случае — «NO».

Related Images:

Mif 6

29/09/2015 by Александр Димитриев

Условие

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Могут ли они быть длинами сторон некоторого треугольника?

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

В одной строке задано три числа [latex]x[/latex], [latex]y[/latex] и [latex]z[/latex].

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

В одной строке вывести «YES»(без кавычек), если являются длинами некоторого невырожденного треугольника, или «NO»(без кавычек), если нет.

Тесты

Входные данные	Выходные данные
1e1000 1e10000 1e-1000	NO
1e100 1e100 1e-100	YES
15.4 6.9 18.3	YES
17.55 37.67 88.98	NO
1000000 200000 30000	NO
1000000 1200000 900000	YES
3 4 5	YES
9 4 3	NO
99 10 47	NO

Код

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

#include <iostream>

using namespace std;

int main() {

long double x,y,z;

cin >> x >> y >> z;

cout << ((x+y>=z)&&(x+z>=y)&&(y+z>=x) ? "YES": "NO");

return 0;

}

Решение

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

Related Images:

ML18

28/09/2015 by Кудымовская Вика

Задача ML18

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

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

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

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex], значения которых не превышают по модулю [latex]100[/latex].

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

Вывести периметр [latex]p[/latex] данного треугольника.

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

Тестирование

№	Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex])	Выходные данные
1	2 2 5 1 0 -1 3 5 10	16.0261556346
2	1 4 5 3 6 0 10.5 -2 -1	31.9047289894
3	15 26 13 32 18 56 80 0 -6.2	212.0962807371
4	-13 68 44 99 -100 70 0 2 1	450.5748518262
5	100 9 17 18 29 88 65 -16 0.36	310.4318979186

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main ()
{
	double x1, x2, x3, y1, y2, y3, z1, z2, z3;
	long double a, b, c, p;
	//стороны AB, BC, AC треугольника ABC обозначим 
	//соответственно, используя переменные a, b, c
	//используем значения переменных с плавающей точкой
	cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;
	a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));
	b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));
	c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));
	p= a + b + c;
	//вычисляем периметр 
	cout << fixed << setprecision(10) << p << endl;
	//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой
	return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main ()

{

double x1, x2, x3, y1, y2, y3, z1, z2, z3;

long double a, b, c, p;

//стороны AB, BC, AC треугольника ABC обозначим

//соответственно, используя переменные a, b, c

//используем значения переменных с плавающей точкой

cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;

a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));

b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));

c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));

p= a + b + c;

//вычисляем периметр

cout << fixed << setprecision(10) << p << endl;

//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой

return 0;

}

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

Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

Подробнее о декартовой системе координат можно прочесть здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

ML23

24/09/2015 by Молоканов Юрий

Условие

Найти длины биссектрис [latex]a_1[/latex], [latex]b_1[/latex], [latex]c_1[/latex] треугольника, если известны длины противоположных сторон [latex]a[/latex], [latex]b[/latex], [latex]c[/latex].

Тестирование

№	Входные данные	Выходные данные
1	6, 7, 9	7.35803, 6.49923, 4.67652
2	3.5, 4.5, 5.5	4.66027, 3.79967, 2.88195
3	100000, 100000, 100000	86602.5, 86602.5, 86602.5
4	1, 1.118034, 1.118034	1, 0.898056, 0.898056

Код

#include <iostream>
#include <cmath>
using namespace std;
 
double getL(double c, double a, double b) {    // Возвращает длину биссектрисы к стороне A при сторонах A, B, C
    double s = a + b;
    return sqrt(a * b * (s + c) * (s - c))/s;  // Формула длины биссектрисы через три стороны
}
 
int main() {
    double a, b, c;
    cin >> a >> b >> c;
    cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double getL(double c, double a, double b) { // Возвращает длину биссектрисы к стороне A при сторонах A, B, C

double s = a + b;

return sqrt(a * b * (s + c) * (s - c))/s; // Формула длины биссектрисы через три стороны

}

int main() {

double a, b, c;

cin >> a >> b >> c;

cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

return 0;

}

Решение

Для вычисления длины биссектрисы через три стороны произвольного треугольника воспользуемся формулой [latex]l_c = \frac{\sqrt{ab(a+b+c)(a+b-c)}}{a+b}[/latex], где:

[latex]l_c[/latex] — длина биссектрисы, проведенной к стороне [latex]c[/latex];
[latex]a[/latex], [latex]b[/latex], [latex]c[/latex] — стороны треугольника.

Формула достаточно громоздкая, а так как использовать мы ее будем трижды — для вычисления длины каждой из биссектрис, — имеет смысл написать функцию, которая бы получала длины трех сторон треугольника и возвращала длину биссектрисы, проведенной к первой из указанных сторон:

double getL(double c, double a, double b) {
	return sqrt(a * b * (a + b + c) * (a + b - c))/(a + b);
}

double getL(double c, double a, double b) {

return sqrt(a * b * (a + b + c) * (a + b - c))/(a + b);

}

Можно заметить, что сумма [latex]a+b[/latex] встречается в формуле три раза. Для лучшей читаемости и компактности кода заменим a + b на s :

double getL(double c, double a, double b) {
    double s = a + b;
    return sqrt(a * b * (s + c) * (s - c))/s;
}

double getL(double c, double a, double b) {

double s = a + b;

return sqrt(a * b * (s + c) * (s - c))/s;

}

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

cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

1	cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

Ссылки

Код программы на Ideone.com;

Формулы длины биссектрис в треугольнике;

Список задач на линейные вычисления.

Related Images:

ML 24

18/09/2015 by Сплошнов Кирилл

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

Треугольник задан длинами сторон. Найти радиус вписанной [latex]r[/latex] и описанной [latex]R[/latex] окружностей.

Тесты :

[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]r[/latex]	[latex]R[/latex]
3	4	5	1	2.5
7.5	10	13	2.45012	6.52361
1	3	4	0	inf
1	1	3	Не существует!	Не существует!

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

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

int main() 
{
	double a, b, c;
	cin >> a >> b >> c;
	if (a + b >= c && b + c >= a && a + c >= b) //проверяем, существует ли треугольник 
	{
		double p = (a + b + c) / 2;
		double S = sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона 
		double r = S / p;
		double R = a* b * c / (4 * S);
		cout<<"Радиус вписанной окружности равен "<<r<<endl;
		cout<<"Радиус описанной окружности равен "<<R<<endl;
	}
	else //если не существует:
		cout<<"Треугольник с заданными сторонами не существует!"<<endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double a, b, c;

cin >> a >> b >> c;

if (a + b >= c && b + c >= a && a + c >= b) //проверяем, существует ли треугольник

{

double p = (a + b + c) / 2;

double S = sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона

double r = S / p;

double R = a* b * c / (4 * S);

cout<<"Радиус вписанной окружности равен "<<r<<endl;

cout<<"Радиус описанной окружности равен "<<R<<endl;

}

else //если не существует:

cout<<"Треугольник с заданными сторонами не существует!"<<endl;

return 0;

}

Алгоритм :

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

	if (a + b >= c && b + c >= a && a + c >= b)//проверяем, существует ли треугольник

9	if (a + b >= c && b + c >= a && a + c >= b)//проверяем, существует ли треугольник

…

	else //если не существует:
		cout<<"Треугольник с заданными сторонами не существует!"<<endl;

else //если не существует:

cout<<"Треугольник с заданными сторонами не существует!"<<endl;

Если треугольник существует, проводим следующие вычисления (порядок сохранен) :

Вычисляем полупериметр [latex]p[/latex] треугольника: [latex]p[/latex] = [latex]\frac{a + b + c}{2}[/latex]
Находим площадь [latex]S[/latex] по формуле Герона: [latex]S[/latex] = [latex]\sqrt{p(p-a)(p-b)(p-c)}[/latex]
Вычисляем радиус [latex]r[/latex] вписанной окружности по формуле: [latex]r[/latex] = [latex]\frac{S}{p}[/latex]
Вычисляем радиус [latex]R[/latex] описанной окружности по формуле: [latex]R[/latex] = [latex]\frac{abc}{4S}[/latex]

Работающая версия программы на Ideaone.com :

Ideone.com

Почитать про треугольник можно здесь :

Треугольник — Википедия

Related Images:

e-olymp 905. Какой треугольник?

14/09/2015 by Алина Гончарова

Задача
Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон.

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

В единственной строке задано 3 целых числа — длины сторон треугольника. Длины сторон не превышают 100.

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

В единственной строке вывести 1, если треугольник равносторонний, 2 если равнобедренный и 3 если разносторонний.

Код

#include <iostream>
using namespace std;
int main() {
	int a,b,c;
	cin>> a >> b >> c;
	if (a==b && b==c && a==c) {
		cout << "1";
	}
	else if (a==b||b==c||a==c) {
		cout << "2";
	}
	else {
		cout << "3";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int a,b,c;

cin>> a >> b >> c;

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

cout << "1";

}

else if (a==b||b==c||a==c) {

cout << "2";

}

else {

cout << "3";

}

return 0;

}

Тесты

№	Входные данные	Выходные данные
1	5 5 5	1
2	4 5 4	2
3	4 5 6	3

Решение

Для решения задачи нам нужно уметь определять виды треугольников. Нам даны равносторонний, равнобедренный и разносторонний треугольники. У равностороннего треугольника все стороны равны, у равнобедренного равны лишь два бедра, а у разностороннего — стороны не равны.

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

если [latex]a=b=c[/latex] , то есть все стороны равны, то у нас равносторонний треугольник;
если[latex] a=b [/latex]или [latex]b=c[/latex] или [latex]a=c[/latex] , то есть две из трех сторон треугольника равны, то у нас равнобедренный треугольник;
если [latex]a\neq b\neq c[/latex] , стороны не равны, то у нас разносторонний треугольник.

Задача взята с сайта.
Переход на страницу с полностью выполненным данным заданием здесь.

Related Images:

Какой треугольник?

01/12/2014 by Зелінський Вячеслав Олександрович

Задача: 905. Какой треугольник? с сайта http://www.e-olimp.com.ua Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон. Существование треугольника и корректность исходных данных гарантируется. Технические условия Входные данные В единственной строке задано 3 целых числа — длины сторон треугольника. Длины сторон не превышают 100. Выходные данные В единственной строке вывести 1, если треугольник равносторонний, 2 если равнобедренный и 3 если разносторонний.

Первая сторона	Вторая сторона	Третья сторона	Результат
2	2	2	1
3	4	3	2
4	7	14	3

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

#include <iostream>

using namespace std;

int main()
{
  int n = 3;
  int a[n];
  for( int i=0 ; i<n ; i++ )
  {
      cin >> a[i];
  }
  if( a[0] == a[1] && a[1] == a[2] )
  {
      cout << 1 << endl;
  }
  else if( a[0] == a[1] || a[1]==a[2] || a[0]==a[2])
  {
      cout << 2 << endl;
  }
  else
  {
      cout << 3 << endl;
  }
  return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n = 3;

int a[n];

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

{

cin >> a[i];

}

if( a[0] == a[1] && a[1] == a[2] )

{

cout << 1 << endl;

}

else if( a[0] == a[1] || a[1]==a[2] || a[0]==a[2])

{

cout << 2 << endl;

}

else

{

cout << 3 << endl;

}

return 0;

}

Задача решена методом моделирования. Вычисления проведены согласно условию, представленному в задаче. По условию задачи необходимо проверить каким является треугольник: равносторонним, равнобедренным или разносторонним. Для этого создаем массив из трех элементов(сторон треугольника), считываем его. Далее, если все элементы массива равны, то треугольник равносторонний, иначе, если две стороны равны, то он равнобедренный, если ни то, ни то не выполняется, то он разносторонний. Для проверки работы программы можно воспользоваться объектом. Ссылка на e-olimp: http://www.e-olymp.com/ru/submissions/2319469 Второй вариант:

#include <iostream>

using namespace std;

int main()
{
   int n = 3;
   int a[n];
   int j = 3;
   for( int i=0 ; i<n ; i++ )
   {
      cin >> a[i];
   }
   if( a[0] == a[1] && a[1] == a[2] )
   {
      cout << 1 << endl;
      return 0;
   }
   int b=0;
   for( int i=0 ; i<n ; i++ )
   {
      if( i+1 != n )
      {
         if( a[i] == a[i+1] )
         {
            b=1;
         }
      }
      else
      {
         if( a[0] == a[2] )
         {
            b=1;
         }
      }
   }
   if( b!=0)
   {
      cout << 2 << endl;
   }
   else
   {
      cout << 3 << endl;
   }
}

#include <iostream>

using namespace std;

int main()

{

int n = 3;

int a[n];

int j = 3;

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

{

cin >> a[i];

}

if( a[0] == a[1] && a[1] == a[2] )

{

cout << 1 << endl;

return 0;

}

int b=0;

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

{

if( i+1 != n )

{

if( a[i] == a[i+1] )

{

b=1;

}

else

{

if( a[0] == a[2] )

{

b=1;

}

if( b!=0)

{

cout << 2 << endl;

}

else

{

cout << 3 << endl;

}

http://www.e-olymp.com/ru/submissions/2319474

Код на Java:

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


class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
           Scanner in = new Scanner(System.in);
           int a, b, c;
           a = in.nextInt(); 
           b = in.nextInt(); 
           c = in.nextInt(); 
           System.out.println(a==b && b==c? 1: a==b || b==c || a==c? 2: 3);	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int a, b, c;

a = in.nextInt();

b = in.nextInt();

c = in.nextInt();

System.out.println(a==b && b==c? 1: a==b || b==c || a==c? 2: 3);

}

Второй вариант:

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
	   int n = 3;
	   Scanner in = new Scanner(System.in);
	   int []a = new int [n];
	   int j = 3;
	   for( int i=0 ; i<n ; i++ )
	   {
	      a[i] = in.nextInt(); 
	   }
	   if( a[0] == a[1] && a[1] == a[2] )
	   {
	      System.out.println(1);
	      return;
	   }
	   int b=0;
	   for( int i=0 ; i<n ; i++ )
	   {
	      if( i+1 != n )
	      {
	         if( a[i] == a[i+1] )
	         {
	            b=1;
	         }
	      }
	      else
	      {
	         if( a[0] == a[2] )
	         {
	            b=1;
	         }
	      }
	   }
	   if( b!=0)
	   {
	      System.out.println(2);
	   }
	   else
	   {
	      System.out.println(3);
	   }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n = 3;

Scanner in = new Scanner(System.in);

int []a = new int [n];

int j = 3;

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

{

a[i] = in.nextInt();

}

if( a[0] == a[1] && a[1] == a[2] )

{

System.out.println(1);

return;

}

int b=0;

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

{

if( i+1 != n )

{

if( a[i] == a[i+1] )

{

b=1;

}

else

{

if( a[0] == a[2] )

{

b=1;

}

if( b!=0)

{

System.out.println(2);

}

else

{

System.out.println(3);

}

Related Images:

Образец: Принадлежит ли точка треугольнику?

12/10/2014 by Мазурок Игорь Евгеньевич

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.

Тесты

В тестах нужно обязательно отразить следующие случаи:

Точка строго вне треугольника
Точка строго внутри треугольника
Точка совпадает с одной из вершин треугольника
Точка лежит на одной из сторон треугольника
Точка лежит на продолжении одной из сторон треугольника
Одна из сторон треугольника параллельна одной из осей координат
Две стороны треугольника параллельны осям координат

xa	ya	xb	yb	yc	xd	yd	Принадлежит?
-1	-1	1	-1	1	2	2	нет
-2	-2	1	-1	1	0	0	да
-1	-1	1	-1	1	0	1	да
-1	-1	1	-1	1	0.5	0	да
-1	-1	1	-1	1	1	3	нет
-1	-1	1	-1	1	0	0	да
0	0	2	0	2	1	1	да
0	0	2	0	2	5	5	нет

Плохое решение

В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.

Неплохое решение

Начнём с простого наблюдения:

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

Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Неважно как называть стороны, важно научиться их различать.

Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].

Обратите внимание, что мы не утверждаем, что для любой точки на прямой наши приближённые вычисления обязаны дать точный ноль. Это было бы неверно. Мы только утверждаем, что если проведенные с доступной нам точностью вычисления всё же дали точный ноль, то мы вынуждены считать данную точку лежащей на данной прямой.

Естественно, что нам придётся записать аналогичные условия для двух оставшихся сторон треугольника (или для всех оставшихся сторон выпуклого многоугольника).

Плохой код

Начнём с того, что объявим переменные и прочитаем их значения. После этого запишем одно очень громоздкое условие, которое и проверяет принадлежность.

#include <stdio.h>

int main() 
{
    double xa, ya, xb, yb, xc, yc, xd, yd;
    scanf ("%lf%lf", &xa, &ya); // читаем координаты точки A
    scanf ("%lf%lf", &xb, &yb); // читаем координаты точки D
    scanf ("%lf%lf", &xc, &yc); // читаем координаты точки C
    scanf ("%lf%lf", &xd, &yd); // читаем координаты точки D
    printf (
    (((xd - xa)*(yb-ya)-(yd-ya)*(xb-xa))*((xc - xa)*(yb-ya)-(yc-ya)*(xb-xa)) >= 0) &&
    (((xd - xb)*(yc-yb)-(yd-yb)*(xc-xb))*((xa - xb)*(yc-yb)-(ya-yb)*(xc-xb)) >= 0) &&
    (((xd - xc)*(ya-yc)-(yd-yc)*(xa-xc))*((xb - xc)*(ya-yc)-(yb-yc)*(xa-xc)) >= 0 )? 
    "yes": "no");
    return 0;
}

#include <stdio.h>

int main()

{

double xa, ya, xb, yb, xc, yc, xd, yd;

scanf ("%lf%lf", &xa, &ya); // читаем координаты точки A

scanf ("%lf%lf", &xb, &yb); // читаем координаты точки D

scanf ("%lf%lf", &xc, &yc); // читаем координаты точки C

scanf ("%lf%lf", &xd, &yd); // читаем координаты точки D

printf (

(((xd - xa)*(yb-ya)-(yd-ya)*(xb-xa))*((xc - xa)*(yb-ya)-(yc-ya)*(xb-xa)) >= 0) &&

(((xd - xb)*(yc-yb)-(yd-yb)*(xc-xb))*((xa - xb)*(yc-yb)-(ya-yb)*(xc-xb)) >= 0) &&

(((xd - xc)*(ya-yc)-(yd-yc)*(xa-xc))*((xb - xc)*(ya-yc)-(yb-yc)*(xa-xc)) >= 0 )?

"yes": "no");

return 0;

}

Нажмите здесь, чтобы выполнить этот код.

Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.

Неплохой код

Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:

#include <stdio.h>

// Вычисляет положение точки D(xd,yd) относительно прямой AB
double g(double xa, double ya, double xb, double yb, double xd, double yd) 
{
    return (xd - xa) * (yb - ya) - (yd - ya) * (xb - xa);
}

// Лежат ли точки C и D с одной стороны прямой (AB)?
bool f(double xa, double ya, double xb, double yb, double xc, double yc, double xd, double yd) 
{
    return g(xa, ya, xb, yb, xc, yc) * g(xa, ya, xb, yb, xd, yd) >= 0;
}

int main() 
{
    double xa, ya, xb, yb, xc, yc, xd, yd;
    scanf("%lf%lf", &xa, &ya); // читаем координаты точки A
    scanf("%lf%lf", &xb, &yb); // читаем координаты точки B
    scanf("%lf%lf", &xc, &yc); // читаем координаты точки C
    scanf("%lf%lf", &xd, &yd); // читаем координаты точки D
    printf( f(xa,ya,xb,yb,xc,yc,xd,yd) && f(xb,yb,xc,yc,xa,ya,xd,yd) && 
            f(xc,yc,xa,ya,xb,yb,xd,yd) ? "yes" : "no");
    return 0;
}

#include <stdio.h>

// Вычисляет положение точки D(xd,yd) относительно прямой AB

double g(double xa, double ya, double xb, double yb, double xd, double yd)

{

return (xd - xa) * (yb - ya) - (yd - ya) * (xb - xa);

}

// Лежат ли точки C и D с одной стороны прямой (AB)?

bool f(double xa, double ya, double xb, double yb, double xc, double yc, double xd, double yd)

{

return g(xa, ya, xb, yb, xc, yc) * g(xa, ya, xb, yb, xd, yd) >= 0;

}

int main()

{

double xa, ya, xb, yb, xc, yc, xd, yd;

scanf("%lf%lf", &xa, &ya); // читаем координаты точки A

scanf("%lf%lf", &xb, &yb); // читаем координаты точки B

scanf("%lf%lf", &xc, &yc); // читаем координаты точки C

scanf("%lf%lf", &xd, &yd); // читаем координаты точки D

printf( f(xa,ya,xb,yb,xc,yc,xd,yd) && f(xb,yb,xc,yc,xa,ya,xd,yd) &&

f(xc,yc,xa,ya,xb,yb,xd,yd) ? "yes" : "no");

return 0;

}

Нажмите здесь, чтобы выполнить этот код.
Трудно сказать, стал ли код боле понятным или лаконичным. Однако можно точно сказать, что в нём отсутствуют повторяющиеся алгоритмические блоки. Все участки кода написаны строго по одному разу. Это уменьшает вероятность ошибки.

Чеширский код

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…

Возможно слишком смело называть это хорошим кодом, но мы сделаем ещё один шаг в нужном направлении. В прошлом коде мы избавились от повторов в кодировании алгоритма. Однако остались повторы в кодировании данных. Вы заметили, что у нас четыре пары переменных? Т.е. просматривается структура состоящая из пары координат x и y, которую стоит объединить и назвать «точкой». Такие структуры в программировании на Си описывают с помощью ключевого слова struct. Это полезная промежуточная структура перед переходом к объектно-ориентированному программированию при помощи классов.

#include <stdio.h>

struct point { double x, y; };

// Читать координаты точки
struct point get() {
    struct point a;
    scanf("%lf%lf", &a.x, &a.y); // читаем координаты точки
    return a;
}

// Вычисляет положение точки D(xd,yd) относительно прямой AB
double g(struct point a, struct point b, struct point d) {
    return (d.x - a.x) * (b.y - a.y) - (d.y - a.y) * (b.x - a.x);
}

// Лежат ли точки C и D с одной стороны прямой (AB)?
bool f(struct point a, struct point b, struct point c, struct point d) {
    return g(a, b, c) * g(a, b, d) >= 0;
}

int main() {
    struct point a = get(), b = get(), c = get(), d = get();
    printf( f(a,b,c,d) && f(b,c,a,d) && f(c,a,b,d) ? "yes" : "no");
    return 0;
}

#include <stdio.h>

struct point { double x, y; };

// Читать координаты точки

struct point get() {

struct point a;

scanf("%lf%lf", &a.x, &a.y); // читаем координаты точки

return a;

}

// Вычисляет положение точки D(xd,yd) относительно прямой AB

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

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

}

// Лежат ли точки C и D с одной стороны прямой (AB)?

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

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

}

int main() {

struct point a = get(), b = get(), c = get(), d = get();

printf( f(a,b,c,d) && f(b,c,a,d) && f(c,a,b,d) ? "yes" : "no");

return 0;

}

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