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

Задача


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

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

Королевство имеет форму треугольника с вершинами [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

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


 

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


Для решения задачи соединим точки  [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

e-olymp 774. Торт

Задача

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

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

Содержит три натуральных числа: радиус стола [latex]r \left(1\leqslant r\leqslant 1000 \right)[/latex], ширину [latex]w[/latex] и длину [latex]l[/latex] торта [latex] \left(1\leqslant w \leqslant l \leqslant 1000\right)[/latex].

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

Вывести слово [latex]YES[/latex], если торт помещается на стол, и слово [latex]NO[/latex] в противном случае.

Тесты

Входные данные Выходные данные
1 38 40 60 YES
2 35 20 70 NO
3 50 60 80 YES
4 30 60 90 NO

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

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

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

 

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

Вписанный в окружность прямоугольник

Вписанный в окружность прямоугольник

Для того, чтобы узнать, помещается торт на столе или нет, необходимо найти диагональ прямоугольного торта. Зная длину и ширину прямоугольника, находим диагональ по теореме Пифагора. Если она равна или меньше диаметра стола $AB^2$ + $AD^2$ <= 4$OD^2$, значит торт помещается, и пишем  "YES". Если диагональ больше диаметра стола, пишем  "NO".

Ссылки

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

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

Задача

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

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

Целочисленные стороны прямоугольника $a$ и $b$ ($1 \leq a$, $b \leq 1000$).

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

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

Тесты

Входные данные Выходные данные
1 3 4 12
2 5 12 60
3 1 1 1
4 1000 1000 1000000

Решение

Для нахождение площади прямоугольника воспользуемся формулой $S = a \cdot b$, где $a$ и $b$ — стороны данного прямоугольника, а $S$ — площадь прямоугольника.

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

Ссылки

e-olymp 7943. Периметр прямоугольника

Задача:

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

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

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

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

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

Тесты:

Входные данные Выходные данные
1 1 4
1000 1000 4000
10 20 60
12 13 50
176 37 426

Решение:

Объяснение: Поскольку стороны прямоугольника, используемые в задаче, целочисленные, и каждое из них меньше [latex]1000[/latex] то переменные создаём типа int. Для решения этой задачи воспользуемся формулой нахождения периметра прямоугольника: [latex] (a+b) \cdot 2 [/latex]

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

Задача

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

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

В первой строке заданы три числа: [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

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

Решение

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

Ссылки

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

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

Задача

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

На границе окружности с центром в начале координат и радиусом $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

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

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

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции  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 12. Поврежденная картина

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

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

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

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

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные Выходные данные
1 1 6 1 4 0 4 5 6 4.000
0 0 6 0 2 0 5 0 5 2.397
2 0 5 0 0 0 6 0 5 4.172
0 0 5 0 2 0 6 0 1 2.058
0 0 10 0 2 0 6 0 1 0.000

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

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее  будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]H[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]H[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]H[/latex]

в таком случае нам необходимо найти дугу [latex]NX_1[/latex],для этого умножив радиус на величину центрального угла: [latex]NX_1[/latex] =[latex]X_0 X_1 \times \arcsin \frac {H}{X_0 X_1}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1.[latex]X_2[/latex]  принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1. [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times \arcsin \frac{X_0 X_3} {X_0 X_1} [/latex]

1.1.2.1.2. [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

1.1.2.1.2.1. [latex]X_0 X_1 < \sqrt{X_0 X_2^2 + H^2} [/latex]

В таком случае искомая величина равна дуге [latex]MN[/latex]= [latex]X_0 X_1 \times  (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{X_0 X_3}  {X_0 X_1}))

1.1.2.2. данный случай аналогичен предыдущему.Единственное различие заключается в том,что точки [latex]X_2[/latex] и [latex]X_3[/latex] меняются местами в формулах.

1.2 [latex]Х_0[/latex]  не принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.2.1 [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times \arccos \frac{A}{X_0 X_1}[/latex]

 

1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times \arcsin \frac{A}{X_0 X_1}[/latex]

1.2.2. обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.2.2.1. [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times  (\arcsin \frac{H}{X_0 X_1} —  \arccos \frac{A}{X_0 X_1})[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

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

 

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

Ссылки

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

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

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

Принадлежит ли точка [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

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

Решение

Для того, чтобы точка [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

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

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

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

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

Целочисленные стороны прямоугольника [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]

 

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

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

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

Ссылки

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

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

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

Задача

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

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

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

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

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

Тесты

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

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

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

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

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


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

Ссылки

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

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

Задача

Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].

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

Два целых числа: [latex]S (0 < S ≤ 100), и[/latex] [latex]a[/latex] ([latex]\left | a \right |[/latex] ≤ 100).

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

Искомая высота с точностью до сотых.

Тесты

# Входные данные Выходные данные
1 20 7 3.73
2 35 3 7.00
3 12 4 3.29
4 67 9 7.92
5 135 13 11.17

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

Алгоритм решения задачи

  1. Формула для вычисления площади треугольника [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot c[/latex], где [latex]h[/latex] – высота, а [latex]c[/latex] – сторона, к которой высота проведена.
  2. В задаче сказано, что основание больше высоты на величину [latex]a[/latex]. Значит вместо [latex]c[/latex] мы можем подставить в формулу [latex]h+a[/latex]. Теперь формула приобретает следующий вид: [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot \left (h+a \right )[/latex]
  3. Cовершив некоторые преобразования приходим к квадратному уравнению [latex]h^{2}+a\cdot h-2\cdot S = 0[/latex]
  4. Далее находим дискриминант по формуле [latex]D = a^{2}+4\cdot2\cdot S[/latex]. Находим корень квадратный из дискриминанта [latex]\sqrt{D}[/latex]
  5. Находим высоту по формуле [latex]h=\frac{-a+\sqrt{D}}{2}[/latex]
  6. Второй корень нам не подходит, потому что он меньше [latex]0[/latex], а длина не может быть отрицательной.
  7. Подставляем исходные данные в формулы, получаем результат.

Также подробное описание представлено в коде программы.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

КМ 29. Монеты

Задача

Задача из журнала «Квант» №6 1970 г. стр. 28 В.И.Арнольд

[latex]n[/latex] одинаковых монет лежат на столе, образую замкнутую цепочку. Сколько оборотов сделает монета [latex]M[/latex] такого же размера за то время, пока она один раз обкатится по внешней стороне всей цепочки, как показано на рисунке (монета [latex]M[/latex] =2 коп.)?
Как изменится ответ, если монета [latex]M[/latex] будет иметь радиус, отличающийся в [latex]k[/latex] раз от радиуса каждой из монет в цепочке?

Условие
Представлю вам предложенное для данной задачи изображение из самого журнала.

Тесты

[su_table]

Входные данные Выходные данные
 № [latex]n[/latex] [latex]k[/latex]  Количество оборотов
 1  3  1  3
 2  12  1  6
 3  182  1  62.667
4  12  2.22 3.19998
 5  145  2.28101  22
 6  8  0.53884  8

 

Код.

 

Решение.

Примем радиус монет, составляющих цепочку, за единицу. За то время, пока монета радиуса [latex]k[/latex] прокатится по дуге [latex]\alpha[/latex] неподвижной окружности радиуса 1, она повернется на угол [latex]\alpha(1+1/k)[/latex] следовательно весь угол на который повернётся монета, равен [latex]\alpha+\alpha/k[/latex](в частности, при [latex]k[/latex]=1 этот угол равен 2[latex]\alpha[/latex]).
Теперь найдем сумму дуг,состоящих из таких точек неподвижных монет, которых монета [latex]M[/latex] касалась при качении по цепочке. Если принять центры монет цепочки за точки [latex]O_1[/latex], [latex]O_2[/latex], … , [latex]O_n[/latex], то сумма дуг, лежащих внутри многоугольника [latex]O_1[/latex][latex]O_2[/latex]…[latex]O_n[/latex], равна сумме его внутренних углов, то есть [latex]\pi(n-2)[/latex]. Сумма дуг, лежащих вне многоугольника, следовательно, равна [latex]\pi(n+2)[/latex].Из неё нужно вычесть ещё сумму дуг лежащих в углублениях между двумя соседними монетами, в которые [latex]M[/latex] не попадает. В каждом из [latex]n[/latex] углублений сумма двух таких дуг равна [latex]2\pi/3[/latex] при [latex]k[/latex]=1 и [latex]2arccos\frac{1}{k+1}[/latex] в общем случае. Итак, сумма дуг, по которым прокатится монета [latex]M[/latex], равна [latex]\pi(n+2)-2\pi n/3[/latex] (в общем случае [latex]\pi(n+2)-2n\arccos\frac{1}{k+1}[/latex]. Чтобы узнать искомое число оборотов, нужно умножить эту велечину на [latex]2[/latex]( в общем случае на [latex]1+1/k[/latex]) и разделить на 2[latex]\pi[/latex].
А значит ответ ([latex]\frac{n}{3}+2[/latex]) оборота при k=1, и [latex]\frac{k+1}{2k}(n-\frac{2}{\pi}n \arccos\frac{1}{k+1}+2)[/latex] оборота в общем случае.

Ссылка на решение:[su_permalink id=»http://ideone.com/zFVl9p» target=»blank»]Ideone[/su_permalink]

A60г

Задача:
Пусть [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]

a60%d0%b3
Тесты:

Вход Выход
[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++:

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

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