e-olymp 8357. Точка в многоугольнике

05/12/2018 by Владислав Шеванов

Задача

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

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

В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

Вывести строку «YES», если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

Входные данные	Выходные данные
3 0 0 1 0 0 1 1 1	NO
4 3 2 0 0 1 5 5 5 6 0	YES
3 5 6 2 3 8 0 -1 -3	NO
4 -2 3 0 0 5 0 0 6 3 3	NO
5 3 1 9 2 3 0 -2 -4 -4 0 -4 5	YES

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

#include <iostream>

using namespace std;

struct point {

int x;

int y;

};

int f (point *p, int N, int x, int y) {

int i1, i2, n, S, S1, S2, S3, flag;

for (n = 0; n < N; n++) {

flag = 0;

i1 = n < N-1 ? n + 1 : 0;

while (flag == 0) {

i2 = i1 + 1;

if (i2 >= N)

i2 = 0;

if (i2 == (n < N-1 ? n + 1 : 0))

break;

S = abs (p[i1].x * (p[i2].y - p[n].y) +

p[i2].x * (p[n].y - p[i1].y) +

p[n].x * (p[i1].y - p[i2].y));

S1 = abs (p[i1].x * (p[i2].y - y) +

p[i2].x * (y - p[i1].y) +

x * (p[i1].y - p[i2].y));

S2 = abs (p[n ].x * (p[i2].y - y) +

p[i2].x * (y - p[n].y) +

x * (p[n].y - p[i2].y));

S3 = abs (p[i1].x * (p[n].y - y) +

p[n].x * (y - p[i1].y) +

x * (p[i1].y - p[n].y));

if (S == S1 + S2 + S3) {

flag = 1;

break;

}

i1++;

if (i1 >= N)

i1 = 0;

}

if (flag == 0)

break;

}

return flag;

}

int main() {

int n, x, y;

cin >> n >> x >> y;

point* p = new point[n];

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

cin >> p[i].x >> p[i].y;

cout << (f(p, n, x, y) ? "YES" : "NO");

return 0;

}

Решение

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

Ссылки

Владислав Шеванов

Псевдо строчная таблица

12/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$	$12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$	$10$
$2 \ 3 \ 5$
$4 \ 4$	$96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$	$6$
$2 \\ 2 \\ 2$
$5 \ 3$	$430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$	$216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$	$945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$	$5$
$5$
$3 \ 7$	$210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$	$202$
$100 \ 1 \\ 100 \ 1$

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

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

long long s[m][n], h=0;

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

{

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

{

cin >> s[i][j];

}

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

{

h+=s[0][i];

}

cout << m*h;

return 0;

}

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

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения

Костя Григорян

Строчная таблица

11/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $1 \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Задача участников — начертить таблицу наименьшей высоты и вычислить ширину каждой ячейки. Алиса очень хочет победить, но она плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит натуральное число $n, \ (1 \leqslant n \leqslant 100).$ Вторая строка содержит $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

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

Тесты

Входные данные	Выходные данные
$3$	$0.1333 \ 0.3333 \ 0.5333$
$2 \ 5 \ 8$
$6$	$0.0736 \ 0.2638 \ 0.3313 \ 0.0736 \ 0.1963 \ 0.0613$
$12 \ 43 \ 54 \ 12 \ 32 \ 10$
$2$	$0.3333 \ 0.6667$
$1 \ 2$
$3$	$0.3333 \ 0.3333 \ 0.3333$
$10 \ 10 \ 10$
$7$	$0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.2500$
$1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 2$
$1$	$1.0000$
$2$
$4$	$0.5102 \ 0.1735 \ 0.2653 \ 0.0510$
$100 \ 34 \ 52 \ 10$
$2$	$0.9901 \ 0.0099$
$100 \ 1$
$6$	$0.0702 \ 0.2515 \ 0.3158 \ 0.0351 \ 0.1287 \ 0.1988$
$12 \ 43 \ 54 \ 6 \ 22 \ 34$
$2$	$0.5000 \ 0.5000$
$2 \ 2$
$10$	$0.0182 \ 0.0364 \ 0.0545 \ 0.0727 \ 0.0909 \ 0.1091 \ 0.1273 \ 0.1455 \ 0.1636 \ 0.1818$
$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10$
$3$	$0.0098 \ 0.9804 \ 0.0098$
$1 \ 100 \ 1$

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

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long double s[n], h=0;

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

{

cin >> s[i];

h+=s[i];

}

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

{

cout.precision(4);

cout << fixed << s[i]/h << " ";

}

return 0;

}

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

Пусть $h=\displaystyle\frac{1}{\gamma}$ — высота таблицы, а $x_1, \ x_2, \ \cdots, \ x_{n-1}, \ 1-x_1-x_2- \cdots -x_{n-1}$ – ширина каждой клетки. Тогда $\displaystyle\frac{x_1}{\gamma} \geqslant s_1, \ \displaystyle\frac{x_2}{\gamma} \geqslant s_2, \ \cdots, \ \displaystyle\frac{x_{n-1}}{\gamma} \geqslant s_{n-1}, \ \displaystyle\frac{1-x_1-x_2- \cdots -x_{n-1}}{\gamma} \geqslant s_n.$ Получаем $x_1 \geqslant s_1\gamma, \ x_2 \geqslant s_2\gamma, \ \cdots, \ x_{n-1} \geqslant s_{n-1}\gamma, \ 1-x_1-x_2- \cdots -x_{n-1} \geqslant s_n\gamma.$
Сделаем из неравенств равенства: $x_1=s_1\gamma+\varepsilon_1, \ x_2=s_2\gamma+\varepsilon_2, \ \cdots, \ x_{n-1}=s_{n-1}\gamma+\varepsilon_{n-1}.$
Имеем
$1-(s_1\gamma+\varepsilon_1)-(s_2\gamma+\varepsilon_2)- \cdots -(s_{n-1}\gamma+\varepsilon_{n-1}) \geqslant s_n\gamma \\
1 \geqslant (s_1+s_2+ \cdots +s_{n-1}+s_n)\gamma+\varepsilon_1+\varepsilon_2+ \cdots +\varepsilon_{n-1}
\\
\gamma \leqslant \displaystyle\frac{1-\varepsilon_1-\varepsilon_2- \cdots -\varepsilon_{n-1}}{s_1+s_2+ \cdots +s_{n-1}+s_n}.$
Максимальное значение $\gamma$ достигается при $\varepsilon_1=\varepsilon_2= \cdots =\varepsilon_{n-1}=0.$ Следовательно $\gamma \leqslant \displaystyle\frac{1}{s_1+s_2+ \cdots +s_{n-1}+s_n},$ а $h=s_1+s_2+ \cdots +s_{n-1}+s_n.$ Тогда ширина каждой ячейки будет равняться $\displaystyle\frac{s_i}{h}$

Ссылки

Код решения

Костя Григорян

e-olymp 48. Красные и синие квадраты

30/06/2018 by Павел Жуков

Задача

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

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

В первой строке находится количество синих квадратов $n$ ($0 < n < 40404$). Далее идут $n$ строк, каждая из которых содержит координаты $x$, $y$ ($-101 \leq x, y \leq 101$) левых нижних углов синих квадратов.

Каждый синий квадрат имеет хотя бы одну общую точку хотя бы с одним другим синим квадратом. Фигура, образованная синими квадратами, является связной.

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

Вывести количество красных квадратов.

Тесты

Входные данные	Выходные данные
$3$ $1$ $2$ $2$ $1$ $3$ $1$	$3$
$3$ $1$ $1$ $2$ $2$ $1$ $3$	$6$
$10$ $1$ $1$ $2$ $2$ $1$ $3$ $2$ $4$ $1$ $5$ $2$ $6$ $1$ $7$ $2$ $8$ $1$ $9$ $2$ $10$	$90$

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

#include <iostream>

using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {

int n;

cin >> n;

for (int i = 0; i < n; ++i){ int x, y; cin >> x >> y;

squares[x + MAX_PAGE_SIZE / 2][y + MAX_PAGE_SIZE / 2] = 1;

}

int perimiter = 0;

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

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

if (squares[i][j]){

perimiter += !squares[i + 1][j] + !squares[i - 1][j] + !squares[i][j + 1] + !squares[i][j - 1];

}

int max = 0;

for (int j = 1; (perimiter - 2 * j) / 2 > 0; ++j){

int i = (perimiter - 2 * j) / 2;

if (i * j - n > max) {

max = i * j - n;

}

cout << max;

return 0;

}

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

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

Чтобы доказать это, пусть сторона квадрата равна $1$. Тогда периметр фигуры, составленной из этих квадратов, всегда будет делится на $2$ (это легко понять, строя такие фигуры на листке бумаги: добавление каждого нового квадрата в фигуру может изменить периметр только на $-4, -2, 0, 2, 4$). А так как периметр прямоугольника равен $2 * (a + b)$, где $a, b$ – стороны прямоугольника, то для существования прямоугольника с таким-же периметром должно выполняться условие $\forall p \in \mathbb{N} , p > 2 \rightarrow \exists a,b \in \mathbb{N} : 2p = 2*( a + b )$. Очевидно, что условие действительно выполняется для всех $p>2$.

Запишем нашу фигуру в массив squares. После чего посчитаем ее периметр: каждый непустой квадратик фигуры добавляет $1$ к периметру за каждую пустую клеточку слева, справа, сверху или снизу от него. Далее будем искать все подходящие прямоугольники, записывая максимальную площадь в переменную max: перебирая значения первой стороны $j$, высчитываем через периметр вторую сторону $i = \displaystyle \frac{p}{2} — j$. Площадь будем считать, как разницу площади прямоугольника и изначальной фигуры (число $n$ равно площади фигуры, потому что площадь каждого квадрата равна $1$).
В конце, выводим разницу максимальной площади и площади изначальной фигуры (площадь изначальной фигуры равна $n$, ведь площадь каждого квадрата равна $1$).

Ссылки

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

Павел Жуков

e-olymp 500. Ремонт

29/06/2018 by Павел Жуков

Задача

Ваш любимый дядя – директор фирмы, которая делает евроремонты в офисах. В связи с финансово-экономическим кризисом, дядюшка решил оптимизировать свое предприятие.

Давно ходят слухи, что бригадир в дядюшкиной фирме покупает лишнее количество стройматериалов, а остатки использует для отделки своей новой дачи. Ваш дядя заинтересовался, сколько в действительности банок краски необходимо для покраски стены в офисе длиной $L$ метров, шириной $W$ и высотой $H$, если одной банки хватает на $16$ метров квадратных, а размерами дверей и окон можно пренебречь? Заказов много, поэтому дядя попросил написать программу, которая будет все это считать.

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

В первой строке содержится количество заказов. Описание каждого заказа состоит из трех натуральных чисел $L$, $W$, $H$ — длины, ширины и высоты офиса в метрах соответственно, каждое из которых не превышает $1000$.

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

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

Тесты

Входные данные	Выходные данные
$1$ $1$ $1$ $1$	$1$
$3$ $8$ $7$ $10$ $15$ $8$ $4$ $3$ $5$ $4$	$19$ $12$ $4$
$2$ $27$ $88$ $19$ $999$ $999$ $999$	$274$ $249501$

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

#include <iostream>

using namespace std;

int main() {

int r;

cin >> r;

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

int l, w, h;

cin >> l >> w >> h;

int s = 2 * h * (w + l);

cout << (s % 16 != 0 ? s / 16 + 1 : s / 16) << endl;

}

return 0;

}

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

Рассчитаем площадь стен комнаты как сумму площадей $4$ прямоугольников: $$hw + hl + hw + hl = 2hw + 2hl = 2h \cdot (w + l)$$ Теперь, зная площадь стен, рассчитаем количество банок краски. Для этого поделим площадь стен на $16$ и округлим вверх. Для округления вверх можно использовать тернарный условный оператор: если $s$ делится нацело на $16$, то ответ будет $\displaystyle \frac{s}{16}$, в противном случае – $\displaystyle \frac{s}{16} + 1$ (деление переменной int – целочисленное). Так как в задаче необходимо обрабатывать несколько таких примеров подряд, то все вычисления взяты в цикл от $0$ до $r$ (название переменной $r$ в самой задаче не указано, оно выбрано произвольно).

Ссылки

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

Павел Жуков

e-olymp 239. Треугольники

19/05/2018 by Андрей Святозар Чернецкий

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные	Выходные данные
5 2 -1 3 0 0 4 -3 0 -2 1	6
5 0 0 2 4 6 6 10 34 -42 -48	10
4 0 0 0 1 1 0 1 1	0
8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2	24
5 0 0 0 1 -1 0 -1 -1 3 -3	3

#include <iostream>

using namespace std;

int main() {

unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};

unsigned long long c = 0;

cin >> n;

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

cin >> x1 >> y1;

if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;

else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;

else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;

else A [3] ++;

}

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

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

if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;

else c += A[i] * (A[i] - 1) * A[j] / 2;

}

cout << c;

return 0;

}

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

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

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

Андрей Святозар Чернецкий

e-olymp 1503. Вписанные треугольники

26/01/2018 by Мороз Дима

Пример первого теста на графике

На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих $C_{n}^3$ треугольников.

Входные данные
Состоит из не более чем $16$ тестов. Каждый тест начинается двумя целыми числами $n \left(0 ≤ n ≤ 500\right)$ и $r \left(0 < r ≤ 100\right)$. Через $n$ обозначено количество точек, а через $r$ радиус окружности. Центр окружности находится в центре координат. Дальше следуют $n$ строк, каждая из которых содержит действительное число $θ \left(0 ≤ θ < 360 \right)$, которое определяет угол в градусах между точкой и направлением $x$-оси. Например, если $θ$ равно $30$ градусов, то соответствующая точка имеет декартовы координаты $\left(r \cdot \cos(30°), r \cdot \sin(30°) \right)$. Последняя строка содержит $n = r = 0$ и не обрабатывается.

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

Тесты

Входные данные	Выходные данные
5 10 10 100 300 310 320 3 20 10 100 300 0 0	286 320
3 5 25 176 243 0 0	25
4 20 30 80 130 330 0 0	822
2 7 30 230 0 0	0

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

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdio.h>

using namespace std;

int main(){

double ang, s, sq, r2, res, M[500];

int n, r, pts;

while(cin >> n >> r, n + r != 0){

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

cin >> M[i];

M[i] = M[i] * M_PI / 180;

}

sort(M, M + n);

res = M_PI * r * r * n * (n - 1) * (n - 2) / 6;

r2 = r * r / 2.0;

sq = M_PI * r * r;

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

for(int j = i + 1; j < n; j++){

ang = M[j] - M[i];

if(ang < M_PI){

s = r2 * (ang - sin(ang));

}else{

ang = 2 * M_PI - ang;

s = sq - r2 * (ang - sin(ang));

}

pts = n - (j - i + 1);

res = res - s * pts;

pts = n - 2 - pts;

res = res - (sq - s) * pts;

}

printf("%.f\n", res);

}

return 0;

}

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

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции sort().

В переменную res изначально заносится площадь, равная площади кругов радиуса $r$,
то есть значение $C_{n}^3 \cdot \pi \cdot r^2 = n(n-1)(n-2)(n-2)\pi \cdot \frac{r^2} {6}$. Значение $\frac{r^2} {2}$ присваивается переменной r2, а sq – площадь одного круга, то есть $\pi \cdot r^2$.

Перебираются пары точек, а затем вычисляется угол.
Если угол меньше, то проходимся по меньшему сегменту, площадь которого равна $\pi r^2-0.5r^2(\alpha-\sin \alpha)$, $\alpha = 2\pi -\alpha$. В ином случае мы проходим по большему сегменту.
В любом случае переменной s присваивается площадь сегмента, который мы проходим от $P_{i}$ к $P_{j}$ при движении против часовой стрелки.

Количество точек, лежащих на сегменте, равно $n-(j-i+1)$.
Значит, из переменной res необходимо вычесть площадь сегмента s такое количество раз, которому равно количество точек, то есть pts .

Количество точек, которые лежат на сегменте площади s , равно $n-2- $ pts.
Площадь противоположного сегмента равна разности площади круга и сегмента. Для получения ответа вычитаем площадь противоположного сегмента из переменной res такое количество раз, которое равно значению переменной pts и выводим полученное значение.

Ссылки

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

Мороз Дима

e-olymp 7944. Площадь прямоугольника

23/12/2017 by Даниил Крутоголов

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex] [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]1[/latex] [latex]1[/latex]	[latex]1[/latex]
2	[latex]2[/latex] [latex]4[/latex]	[latex]8[/latex]
3	[latex]511[/latex] [latex]428[/latex]	[latex]218708[/latex]
4	[latex]5555[/latex] [latex]4444[/latex]	[latex]24686420[/latex]
5	[latex]11[/latex] [latex]11[/latex]	[latex]121[/latex]

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

#include <iostream>

using namespace std;

int main()

{

int a, b;

cin >> a >> b;

cout << a * b << endl;

return 0;

}

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

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Даниил Крутоголов

e-olymp 926. Формула Герона

23/11/2017 by Артем Чернобровкин

Задача

Герон Александрийский

Задано стороны [latex]a, b, c, d[/latex] и диагональ [latex]f[/latex] выпуклого четырехугольника. Определить площадь четырехугольника, используя вспомогательную функцию вычисления площади треугольника по формуле Герона.

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

В одной строке задано 5 действительных чисел [latex] a, b, с, d, f[/latex] [latex](0 < a, b, c, d, f ≤ 100)[/latex], как показано на рисунке.

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

Вывести площадь четырехугольника с точностью 4 знака после десятичной точки.

Тесты

#	Входные данные	Выходные данные
1	2 2 2 2 2	3.4641
2	7 7 5 6 2	11.6120
3	9 5 3 2 4	2.9047
4	5 7 2 3 4	12.7027
5	7 8 6 2 5	22.0043

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

#include <iostream>

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

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

using namespace std;

int main() {

double a,b,c,d,f;//длины сторон треугольника

double S1,S2,SO;//площади треугольников и общая площадь соответственно

double P1,P2,p1,p2;//периметр и полупериметр соотвественно

double G1,G2;//выражение под корнем

cin>>a>>b>>c>>d>>f;

P1= a+b+f;//периметр первого треугольника

p1= P1/2;//полупериметр первого треугольника

P2= d+c+f;//периметр второго треугольника

p2= P2/2;//полупериметр второго треугольника

G1=p1*(p1-a)*(p1-b)*(p1-f);//выражение под корнем

S1=sqrt(G1);//пользуясь формулой Герона извлекаем корень

//аналогично для второго треугольника

G2=p2*(p2-d)*(p2-c)*(p2-f);

S2=sqrt(G2);

SO=S1+S2;//находим общую площадь фигуры состоящую из двух треугольников

cout<<fixed<<setprecision(4)<<SO;

return 0;

}

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

Дано

Фигура, состоящая из двух треугольников;

Цель

Посчитать площадь данной фигуры;

Идея

Разбить фигуру на два треугольника и посчитать площадь каждого в отдельности, а потом сложить.

Способ решения

Вспомним формулу Герона [latex] S = \sqrt{p \cdot(p-a) \cdot(p-b) \cdot(p-c)}[/latex].
Поймем, что нам не хватает некоторых данных, а именно [latex]p[/latex].
Понимаем, что [latex]p[/latex] — это полупериметр, который находится по формуле [latex]p=\frac{P}{2}[/latex].
Возникает вопрос, что такое [latex]P[/latex] ? Приходим к выводу, что это периметр.
Находим формулу периметра, который равен [latex]P=a+b+c[/latex]. Данная формула была подведена под условие нашей задачи.
После того как мы вывели формулы, можем приступать к решению задачи.
Подставляя исходные данные в формулы, которые были представлены выше, получаем результат.
Более подробное описание каждого действия представлено выше в коде. Это сделано для того, чтобы пользователь получал ответы на интересующие его вопросы непосредственно в момент их возникновения.

Ссылки

Задача на e-olymp

Код задачи на ideone

Артем Чернобровкин

e-olimp 146. Квадраты — 2

04/11/2017 by Антон Джашимов

Задача

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

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

Во входном файле одно число [latex]N[/latex]. [latex]1 ≤ N ≤ 100[/latex].

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

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

Тесты

Входные данные	Выходные данные
1	50.00000
3	65.62500
10	66.66660
50	66.66667
100	66.66667

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

#include <iostream>

#include <cmath>

#include <iomanip>

//Подключаем этот модуль,чтобы установить точность ответа

using namespace std;

int main() {

double n;

cin >> n;

cout << fixed << setprecision(5) << (50*(1-(pow(0.25,n))))/(0.75);

return 0;

}

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

При [latex]N=1[/latex] площадь черной фигуры составляет [latex]50\%[/latex]. При [latex]N=2[/latex] площадь фигуры равна [latex]50\%+50\%\cdot 1/4[/latex]. При [latex]N=3[/latex] площадь черной фигуры составляет [latex]50\%+50\%\cdot 1/4+50\%\cdot 1/16[/latex]. Очевидно, что перед нами геометрическая прогрессия. Процент, занимаемый площадью черной фигуры, будем искать через сумму геометрической прогресcии: [latex]S_n={{b_1(1-q^N)}\over{1-q}}[/latex], где [latex]q={{b_2}\over{b_1}}={{12.5}\over{50}}=0.25[/latex], [latex]N-[/latex]кол-во операций.

Ссылки

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

Антон Джашимов

A60г

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

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

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

Тесты:

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

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

#include <iostream>

#include <cmath>

using namespace std;

int main() {

float x, y, u;

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

float a=x*x+y*y;

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

{

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

}

else

{

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

}

return 0;

}

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

float x = in.nextFloat();

float y = in.nextFloat();

float a=x*x+y*y;

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

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

}

else{

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

}

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

Алла Марокко

KM63

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

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

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

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

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

Тесты

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

Код задачи

#include <iostream>

using namespace std;

int main() {

long long m,n;

cin>>m>>n;

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

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

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

return 0;

}

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

}

else{

cout<<"No";

}

return 0;

}

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

Курьянов Павел

ML39. Старинное окно

28/09/2016 by Тимур Фирсов

Задача

Окно в университетской аудитории имеет форму прямоугольника с присоединенным в верхней части полукругом. Периметр всего окна равен [latex]P[/latex]. Определить радиус полукруга [latex]R[/latex], при котором площадь окна максимальна.
Входные данные: Периметр окна [latex]P[/latex].
Выходные данные: Радиус полукруга [latex]R.[/latex]

Тесты

	Входные данные	Выходные данные
№	[latex]P[/latex]	[latex]R[/latex]
1	100	14.0025
2	73	10.2218
3	14	1.96035
4	0	0

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

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double P, R;

cin>>P;

R=P/(4+M_PI);

cout<<R;

return 0;

}

Решение

Университетское окно

Обозначим боковую сторону окна [latex]b[/latex], а нижнюю [latex]a[/latex]. [latex]R=\frac { a }{ 2 } [/latex], тогда периметр окна [latex]P=a+2b+\frac { \pi a }{ 2 } [/latex], а площадь равна сумме площадей прямоугольника и полукруга [latex]S=ab+\frac { \pi { a }^{ 2 } }{ 8 } [/latex]. Выразим сторону [latex]b[/latex] через [latex]a[/latex] и периметр [latex]P[/latex] : [latex]b=\frac { 2P-2a-\pi a }{ 4 } [/latex], тогда [latex]S=\frac { 4Pa-4a^{ 2 }-\pi a^{ 2 } }{ 8 } [/latex]. Вычислим производную функции [latex]S(a)[/latex]. [latex]S'(a)=\frac { 2P-4a-\pi a }{ 4 } [/latex], затем найдем точки экстремума функции:
[latex]\frac { 2P-4a-\pi a }{ 4 } =0[/latex], тогда [latex]a=\frac { 2P }{ 4+\pi } [/latex].
Найдём область допустимых значений для [latex]a[/latex]. Наибольшего значения [latex]a[/latex] достигает при [latex]b=0[/latex], [latex]P=a+ \frac {\pi a}{2}[/latex], соответственно [latex]a=\frac { 2P }{ 1+\pi } [/latex]. Значит областью допустимых значений является отрезок [latex][0; \frac { 2P }{ 2+\pi } ] [/latex]. Поскольку [latex]0 < \frac { 2P }{ 4+\pi } < \frac { 2P }{ 2+\pi }[/latex] делаем вывод, что [latex]a=\frac { 2P }{ 4+\pi } [/latex] попадет в область допустимых значений. Найдём максимальное значение функции на отрезке:
[latex]S(0)=0[/latex].
[latex]S(\frac { 2P }{ 4+\pi })= \frac { 4P ^ {2} }{ 32 + 8 \pi } [/latex].
[latex]S( \frac { 2P }{ 2+\pi })= \frac { 4P ^ {2} }{ 16 + 8 \pi } \cdot \frac { \pi }{ 2+ \pi } [/latex].
[latex] \frac {S(\frac { 2P }{ 4+\pi })}{S( \frac { 2P }{ 2+\pi })} = \frac { 4+4\pi +{ \pi }^{ 2 } }{ 4\pi +{ \pi }^{ 2 } } [/latex].
Тогда [latex]S(0) < S(\frac { 2P }{ 2+\pi }) < S(\frac { 2P }{ 4+\pi }) [/latex].
Значит площадь окна [latex]S[/latex] достигает максимального значения при [latex]a=\frac { 2P }{ 4+\pi }[/latex], из чего следует [latex]R=\frac { P }{ 4+\pi }[/latex].

Ссылка на код

ideone

Тимур Фирсов

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;

}

Код на 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) ;//выведем её результат

}

Решение:
Координаты векторов находим по формуле:
[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 .
Онлайн калькулятор .

Алла Марокко

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;

}

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

Используя известные нам координаты вершин треугольника и формулу вычисления расстояния между двумя точками в пространстве [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

Даниил Юдин

ML6

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

Условие

Даны катеты прямоугольного треугольника. Найти его гипотенузу и площадь.

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

В одной строке задано два числа — катеты прямоугольного треугольника соответственно [latex]a[/latex] и [latex]b[/latex]. Значения катетов не превышают по модулю [latex]100[/latex].

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

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

Тесты

Входные данные	Выходные данные
3 4	5.00 6.00
10 10	14.14 50.00
50 90	102.96 2250.00
1 1	1.41 0.50
9 99	99.41 445.50
12 16	20.00 96.00
9 12	15.00 54.00
25 50	55.90 625.00
56 42	70.00 1176.00

Код

#include <iostream>

#include <math.h>

#include <iomanip>

using namespace std;

int main () {

double a,b;

cin >> a >> b;

cout << fixed << setprecision(2) << sqrt(a*a+b*b) << " " << a*b/2 << endl;

return 0;

}

Решение

Каждый в школе узнает как найти гипотенузу и площадь прямоугольного треугольника. Для того чтобы найти гипотенузу надо использовать теорему Пифагора [latex]c^2=a^2+b^2\rightarrow\sqrt(a^2+b^2)[/latex], а для нахождения площади — формулу [latex]a\cdot b/2[/latex].
Код программы

Александр Димитриев

ML3

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

Задача

Дана длина ребра куба. Найти объем куба и площадь его полной поверхности.

Входные данные: задаем число [latex] a [/latex].

Выходные данные: получаем объем куба и площадь его боковой поверхности.

Тесты

Ввод:	2	3	4	7
Вывод:	24 8	54 27	96 64	294 343

#include <iostream>

using namespace std;

int main() {

double a;

cin >> a;

cout << 6 * a * a << " " << a * a * a;

return 0;

}

На входе программа считывает введенное нами число, и после выводит по формуле 2 нужных нам числа в разных строчках.

Кирилл Демиденко

ML19

18/09/2015 by Таран Таня

Задача. Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.

Тесты

Длина окружности	Точность	Результат работы программы
0	3	Невозможно выполнить для вырожденной окружности
-1	8	Ошибка ввода данных
34	-5	Ошибка ввода данных
25	18	Вывод с заданной точностью невозможен. Максимально возможная точность 13
25	13	49.7359197162173
83	5	548.20920
113.42	3	1 023.692
12 345 678	3	Вывод с заданной точностью невозможен. Максимально возможная точность 1
12 345 678	1	12 128 861 224 697.9
1 000 000 000	0	Число содержит больше 15 значащих цифр. Точный вывод невозможен

Алгоритм

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

Для удобства преобразуем известные нам формулы:

[latex]L = 2 \pi \cdot R[/latex] [latex]S = \pi \cdot R^2 [/latex] [latex] \longrightarrow[/latex] [latex]R= \frac{L}{2\pi}[/latex] [latex]\longrightarrow[/latex] [latex]S = \frac{L^2}{4\pi}[/latex];

Воспользовавшись данной формулой находим искомую величину. Однако реализуя вывод с заданной точностью, требуется проверить сможет ли используемый нами тип данных double его обеспечить. Принимая во внимание факт, что данный тип хранит не более чем [latex]15[/latex] значащих десятичных цифр осуществляем следующую последовательность действий:

Находим значение переменной possibleAccuracy как разность между максимально возможным количеством значащих цифр (maxAccuracy = [latex]15[/latex]) и имеющемся в данном числе .
Отрицательное значение переменной possibleAccuracy сигнализирует о том, что найденная площадь круга превышает [latex] 10^{15} [/latex]. Следовательно, выводим предупреждение о том, что точный подсчет невозможен даже с нулевой точностью после запятой.
При условии, что запрашиваемая точность превышает максимальную, выводим уведомление и значение максимальной точности.
При ложности пункта 2 и 3, используя манипулятор setprecision, выводим нужное количество знаков.

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

#include <iostream>

#include <iomanip>

#include <math.h>

using namespace std;

const int maxAccuracy = 15;

int main() {

double circumference, circleArea;

int givenAccuracy, possibleAccuracy;// заданная пользователем и максимально возможная в данном случае точность соответственно

cin >> circumference >> givenAccuracy;

if (circumference == 0)

cout << "Невозможно выполнить для вырожденной окружности";// выведение уведомления, если задана вырожденная окружность

else if (circumference < 0 || givenAccuracy < 0){

cout << "Ошибка ввода данных";// проверка введенных данных

} else {

circleArea = circumference * (circumference / (4 * M_PI));

possibleAccuracy = maxAccuracy - ceil(log10(circleArea));

if (possibleAccuracy < 0)

cout << "Число содержит больше 15 значащих цифр. Точный вывод невозможен";// предупреждение, если число превышает 10^15

else if (possibleAccuracy < givenAccuracy)

cout << "Вывод с заданной точностью невозможен. Максимально возможная точность " << possibleAccuracy;

else

cout << fixed << setprecision(givenAccuracy) << circleArea;

}

return 0;

}

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

Таран Таня

http://www.e-olymp.com/ru/users/TT13

Ю1.26

21/12/2014 by Сіренко Валерія Сергіївна

Задача:

Треугольник задается координатами своих вершин на плоскости : [latex]A(x_{1} , y_{2})[/latex] , [latex]B(x_{2} , y_{2})[/latex] , [latex]C(x_{3} , y_{3})[/latex] . Найти длину и основание высоты, опущенной из вершины A на сторону ВС.

Тесты

[latex]x_{А}[/latex]	[latex]y_{A}[/latex]	[latex]x_{B}[/latex]	[latex]y_{B}[/latex]	[latex]x_{C}[/latex]	[latex]y_{C}[/latex]	Основание ([latex]BC[/latex])	Высота[latex]h[/latex]	Комментарий
7	9	45	9	34	5	11	13	пройден
0.75	1	0.25	2	0.5	3	1	0	пройден
98	67	56	47	34	95	52	47	пройден
0	1	0	3	0	4	1	0	пройден

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

Код:

#include <iostream>

#include <math.h>

using namespace std;

int main(){

double xA, yA, xB, yB, xC, yC; int h, S, AB, BC, AC;

cin>>xA>>yA>>xB>>yB>>xC>>yC;

AB = sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));

BC = sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));

AC = sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));

{

if((AB>BC+AC)&&(BC>AB+AC)&&(AC>AB+BC))

{

cout << ("Treygolnik ne syshestvyet");

}

else

{

S = fabs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))/2.0;

h = (2*S)/ BC;

cout << BC << " " << h;

}

return 0;

}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone

{

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

{

double xA, yA, xB, yB, xC, yC; double h, S, AB, BC, AC;

Scanner in = new Scanner(System.in);

xA = in.nextDouble();

yA = in.nextDouble();

xB = in.nextDouble();

yB = in.nextDouble();

xC = in.nextDouble();

yC = in.nextDouble();

AB = Math.sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));

BC = Math.sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));

AC = Math.sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));

if((AB>BC+AC)&&(BC>AB+AC)&&(AC>AB+BC))

{

System.out.printf("Treygolnik ne syshestvyet");

}

else

{

S = Math.abs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))/2.0;

h = (2*S)/ BC;

System.out.printf("BC");

System.out.printf(" ");

System.out.printf("%.1f",h);

}

ссылка на C++ : http://ideone.com/fBfd8S

ссылка на Java : http://ideone.com/ut9G6J

Решение:

Для начала находим стороны треугольника :

AB = sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));

BC = sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));

AC = sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));

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

18	S = fabs((xB-xA)(yC-yA)-(xC-xA)(yB-yA))/2.0;

и с помощью площади находим высоту :

19	h = (2*S)/ BC;

и в конце выводим высоту и основание.

Сіренко Валерія Сергіївна

А26

23/10/2014 by Гусак Дмитро Євгенович

Задача:

Найти площадь сектора, радиус которого равен 13.7, а дуга содержит заданное число радиан [latex] \varphi[/latex].

Тесты:

Ввод	Вывод	Результат
1	93.845	Площадь найдена
-1	Неверный ввод	Неправильные данные, подсчет невозможен
0.7	65.691	Площадь найдена
8.36	784.544	Площадь найдена
0	Неверный ввод	Неправильные данные, подсчет невозможен
3.14	294.673	Площадь найдена

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

#include <iostream>

using namespace std;

int main() {

double r = 13.7; //заданный радиус

double radian; //угол, вводимый вручную

double square; //площадь, выводимая на экран

printf("Введите число радиан дуги:");

scanf("%lf", &radian);

if(radian <= 0)

{

printf("Неверный ввод \n");

}

else

{

square = radian/2 * (r*r);

printf("%5.3lf \n",square);

}

return 0;

}

Решение:
Площадь сектора находится по формуле [latex]S=\frac{\varphi}{2}r^2[/latex], после чего выводится на экран. В случае, если введённый угол меньше или равен нулю, программа выдает сообщение о неверном вводе.

Использованную формулу можно найти по этой ссылке, а здесь находится код в Ideone.

Гусак Дмитро Євгенович