e-olymp 2501. Круговая диаграмма

Задача


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

Исходными данными для этой диаграммы является набор чисел $a_1,\ldots, a_n, а$ диаграмма представляет собой круг радиуса $r$, разделенный на секторы. При этом каждому из чисел соответствует ровно один сектор, площадь которого пропорциональна этому числу. Общая площадь секторов равна площади круга.

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

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

Первая строка содержит два целых числа $n$ и $r \space (1 \leq n, r \leq 100)$. Вторая строка содержит $n$ целых чисел $a_1,\ldots, a_n \space (1 \leq a_i \leq 100$ для всех $i$ от $1$ до $n)$.

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

Выведите $n$ вещественных чисел — площади секторов, соответствующих числам $a_1,\ldots, a_n$. Выводите каждое из чисел в отдельной строке.

Все эти числа должны быть выведены с точностью не хуже $10^{-6}$.

Тесты

Входные данные Выходные данные
3 2
1 4 3
1.570796327
6.283185307
4.712388980
2 3
3 8
7.711181968
20.563151914
4 5
2 5 9 1
9.239978393
23.099945982
41.579902768
4.619989196
5 9
4 16 8 20 11
17.252135928
69.008543713
34.504271856
86.260679641
47.443373803

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

Решение

Найдем сперва сумму всех чисел $a_i$ и площадь диаграммы (по известной формуле площади круга). Теперь можем легко посчитать площади каждого из секторов нашей диаграммы, разделив площадь последней на ранее найденную сумму и умножив их частное на соответствующее число $a_i$.

Ссылки

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

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

Задача взята с сайта 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

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

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

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

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

Ссылки

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

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

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

e-olymp 1507. История Лаурела-Харди

Задача

Лаурел и Харди — два известных киногероя $50$-ых. Они известны своей разницей в весе, как можно увидеть на картинке. Если Вы еще не разобрались, кто из них кто, то я добавлю, что Лаурел легче. В свои юношеские годы Лаурел и Харди любили играть со странными качелями, и когда качели находились в равновесии, то Харди всегда был у земли. Мы рассмотрим двумерную версию качель.

Качели, которыми пользовались Лаурел и Харди, представляют собой часть окружности радиуса $r$, как показано на картинке (они закрашены серым и имеют вид буквы $D$). Харди сел на точку $B$ (самая правая точка качель), а Лаурел сел на точку $A$ (самая левая точка отрезка $AB$). $d = EF$ — расстояние между центром отрезка $AB$ и дуги $AFB$. То есть $E$ — середина отрезка $AB$, а $F$ — середина дуги $AFB$. $MN$ — основа качель, является горизонтальной прямой. $BD = h_1$ — расстояние от Харди до земли. Вам необходимо найти расстояние от Лаурела до земли (обозначаемое $h_2 = AC$).

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

Первая строка содержит количество тестов $N \space (0 < N ≤ 1000)$. Каждая из следующих $N$ строк представляет собой отдельный тест, который имеет следующий формат:

Каждая строка содержит три целых числа $r \space (10 ≤ r ≤ 100), \space$ $d \space (5 ≤ d ≤ r), \space$ $h_1 \space (5 ≤ h_1 ≤ d)$. Значение этих чисел приведено выше.

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

Для каждого теста в отдельной строке вывести его номер и действительной число — значение $h_2$. Это число должно содержать четыре десятичных знака. Формат вывода приведен в примере.

Тесты

Входные данные Выходные данные
2
10 10 10
10 7 6
Case 1: 10.0000
Case 2: 8.0342
3
12 7 7
11 11 8
54 12 6
Case 1: 7.0000
Case 2: 14.0000
Case 3: 19.7383
5
94 21 12
23 9 8
5 4 3
2 2 1
43 26 20
Case 1: 32.1226
Case 2: 10.0439
Case 3: 5.0440
Case 4: 3.0000
Case 5: 32.4231

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

Решение

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

В $9$ строке введем число $N$ из входного потока, а в $10$ — запустим цикл, который будет работать $N$ раз. Далее за каждый проход цикла будем читать по $3$ следующих числа из входного потока и выводить на экран номер текущего теста. Перед тем, как идти дальше, разберемся в рисунке. Так как по условию отрезок $EF$ делит сегмент $AFB$ пополам, то по свойствам хорд и дуг окружности, он является частью радиуса $r$ нашей окружности с центром в точке $O$ и перпендикулярен хорде $AB$, что и показано на чертеже. Кроме того, я дорисовал радиусы $OA$ и $OB$ окружности к соответствующим точкам и начертил отрезок $BH$, как продолжение $AB$, от точки $B$ до прямой $MN$. Также, я построил прямоугольный треугольник $\triangle OGB$, в котором катет $OG = r-BD$.
Достроив все необходимые отрезки, легко заметить, что мы имеем прямоугольный треугольник $\triangle ACH$ с катетом $AC$, длину которого нам и нужно найти по условию задачи. Предлагаю сделать это, воспользовавшись формулой $AC = AH \cdot \sin(\angle AHC)$. Найдем значения сомножителей.

Из рисунка очевидно, что $\angle AHC = \angle BHD = \angle EBG = \angle OBG-\angle OBE.$
Сначала найдем $\angle OBG$. Для этого рассмотрим треугольник $\triangle OGB$. Длины его гипотенузы и противолежащего к искомому углу катета нам уже известны, так что можем сразу найти $\angle OBG = \arcsin \frac{OG}{OB}$.
Теперь найдем $\angle OBE$. Рассмотрим прямоугольный треугольник $\triangle OEB$. В нем противолежащий искомому углу катет $OE = r-d$, а гипотенуза $OB = r$. Значит, $\angle OBE = \arcsin \frac{OE}{OB}$.
В итоге остаётся только найти разницу этих углов, которая и будет являться величиной искомого $\angle AHC$. В коде же значение этого угла считается в $13$ строке и присваивается переменной a.

Стоит заметить, что если $\angle OBG-\angle OBE = 0$, то длины отрезков $AC$ и $BD$, очевидно, совпадают. В таком случае можем сразу вывести на экран $h_2 = h_1$, как мы и поступили в $15$ строке, и перейти к нахождению $AC$ уже для следующего тестового случая.

Если же величина $\angle AHC$ отлична от $0$, то нам все еще предстоит посчитать длину гипотенузы $AH$ треугольника $\triangle ACH$. Она состоит из хорды $AB$ и отрезка $BH$.
Сперва найдем длину хорды. Известно, что $OF$ делит ее на $2$ одинаковых по длине отрезка, значит, следует опять рассмотреть треугольник $\triangle OEB$. Длину его гипотенузы и одного из катетов мы уже находили, так что просто применим теорему Пифагора и найдем $EB = \sqrt{OB^2-OE^2}$. Тогда $AB = 2 \cdot EB$.
Для нахождения длины $BH$, рассмотрим треугольник $\triangle BDH$, в котором этот отрезок является гипотенузой. Длину катета $BD$ и величину угла $\angle BHD$ мы уже знаем, значит, можем применить формулу $BH = \frac{BD}{\sin(\angle BHD)}$.
Сложим найденные значения длин хорды $AB$ и отрезка $BH$, чтобы получить $AH$. В коде эта длина находится в $17$ строке и присваивается переменной b.

Теперь остается только подставить найденные значения в ранее приведенную формулу и получить наконец длину $h_2$, которую выведем на экран в $18$ строке.

Ссылки

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

e-olymp 52. Сыр для Анфисы

Сыр для Анфисы

Готовя обед для Анфисы — символа 2008 года, хозяин использовал для разрезания сыра специальный нож, который разрезал сыр на одинаковые прямоугольные паралелепипеды с основанием в виде квадрата со стороной [latex]a[/latex] и высотой [latex]b[/latex].
Но Анфиса, как и подобает даме года, любила употреблять сыр несколько меньших размеров, для чего она всегда разрезала предложенный кусочек деликатеса на две части, предварительно установив его строго вертикально квадратом к столу. При разрезании нож всегда размещался по диагонали квадрата, но Анфисе не всегда удавалось разрезать кусочек пополам, так как плоскость лезвия ножа образовывала двугранный угол [latex]z^o[/latex] с плоскостью основания.
Найти площадь [latex]s[/latex] созданного Анфисой сечения.

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

Целые числа [latex]a[/latex], [latex]b[/latex], [latex]z[/latex], не превышающие [latex]90^o[/latex].

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

Площадь [latex]s[/latex] образованного сечения с точностью до трех десятичных знаков.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]2[/latex] [latex]3[/latex] [latex]90[/latex] [latex]8.485[/latex]
2 [latex]2[/latex] [latex]4[/latex] [latex]0[/latex] [latex]0.000[/latex]
3 [latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]0.501[/latex]
4 [latex]1[/latex] [latex]1[/latex] [latex]100[/latex] [latex]1.615[/latex]
5 [latex]3[/latex] [latex]10[/latex] [latex]48[/latex] [latex]6.725[/latex]

 

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

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

Для решения данной задачи нам нужно рассмотреть 4 случая:
1) Если [latex]\cot[/latex] заданного угла не будет превышать [latex]\frac{a} {\sqrt{2} \cdot b}[/latex] и также не будет равен [latex]0^o[/latex] и [latex]90^o[/latex], то фигурой сечения получится треугольник. Его площадь мы сможем найти по формуле [latex]s = \frac {a^{2}} {2 \cos (z \cdot \frac {\pi} {180})}[/latex].
2) Заданный угол = [latex]0^o[/latex], следовательно площадь сечения также будет = 0, так как сыр нормально и не порежут.
3) Заданный угол = [latex]90^o[/latex], фигурой сечения будет прямоугольник, площадь которого мы сможем найти по формуле [latex]s = a \cdot b \cdot \sqrt{2}[/latex].
4) В любом другом случае, получится трапеция, площадь которой мы найдем по формуле [latex]s = \frac {a \cdot \sqrt{2} — b \cdot 1} {tan(z \cdot \frac{\pi}{180})} \cdot \frac {b} {sin (z \cdot \frac {\pi}{180})}[/latex].

Ссылки

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

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

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

Задача

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

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

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

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

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

Тесты

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

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

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

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

Ссылки

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

e-olymp 76. Новый шкаф

ЗадачаНовый шкаф

Заданы размеры прямоугольной двери [latex]a[/latex], [latex]b[/latex] и размеры шкафа, который имеет форму прямоугольного параллелепипеда [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Можно ли пронести шкаф сквозь дверь, если проносить его разрешается так, чтобы каждое ребро шкафа было параллельно или перпендикулярно стороне двери.

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

Пять действительных чисел [latex]a[/latex], [latex]b[/latex], [latex]x[/latex], [latex]y[/latex], [latex]z[/latex] ( [latex] 0\;\lt\;a,\;b,\;x,\;y,\;z\;\lt\;10[/latex] ).

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

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

Тесты

Входные данные Выходные данные
[latex]5\;7\;4\;6\;8[/latex] [latex]1[/latex]
[latex]1\;4\;2\;3\;6[/latex] [latex]0[/latex]
[latex]2.9\;6.7\;5.1\;3.7\;1.0[/latex] [latex]1[/latex]
[latex]4\;6\;6\;4\;3[/latex] [latex]1[/latex]
[latex]1.5\;8\;9.9\;2\;7.5[/latex] [latex]0[/latex]
[latex]2\;2\;2\;2\;2[/latex] [latex]0[/latex]
[latex]2\;3\;7\;8\;8[/latex] [latex]0[/latex]
[latex]5\;6\;2\;4\;3.5[/latex] [latex]1[/latex]

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

Решение

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

Имеем шесть возможных вариантов ширины и высоты грани шкафа — [latex](x,y)[/latex], [latex](y,x)[/latex], [latex](y,z)[/latex], [latex](z,y)[/latex], [latex](x,z)[/latex], [latex](z,x)[/latex]

Сравнивая их с размерами двери определяем, можно ли пронести шкаф сквозь дверь.

Ссылки

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