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

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

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

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

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

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

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

ml38

Тесты.

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

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

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

Решение.

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

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

Mif 17.12

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

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

Код

 

Тесты

Входные данные
Выходные данные
x y
9 0 No
-5 3 No
1 2 Yes
-3 5 Yes
1 -1 Yes
4 -4 No

Решение

  1. Сначала ищем длину отрезка ([latex] a [/latex]) от начала координат к точке [latex] (x;y) [/latex]  по формуле: [latex]\sqrt{{({x}_{0}-x)}^{2}+{({y}_{0}-y)}^{2}}[/latex], где              [latex]({x}_{0};{y}_{0})[/latex] — координаты начала координат.
  2.  Дальше проверяем, если [latex]a^{2}\leq 36[/latex] (т.е. точка находится в круге, т.к радиус четверти круга равен 6, а, возведя [latex]a[/latex] в квадрат, радиус также нужно возвести в квадрат) и [latex] (x;y) [/latex] находятся в первой четверти координат, то программа выводит «Yes» (можем возвести радиус ([latex] a=\sqrt{x^{2}+y^{2}} [/latex] )в квадрат,т.к. радиус не может быть отрицательным).
  3. Также, если сумма [latex] x + y [/latex] в четвертой четверти координат не превышает 6, то точка принадлежит треугольнику и программа выводит «Yes».
  4. В том случае, если тока не принадлежит фигуре, программа выводит «No».

Ссылки

 

Mif 17.5

Условие

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

рисунок 17.5

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

Координаты точки [latex]\left(x,y\right)[/latex] на плоскости.

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

Если точка принадлежит фигуре, вывести «Принадлежит» (без кавычек), в противном случае — «Не принадлежит».

Задача взята отсюда.

Тесты

x y Вывод
1 1 -1 Принадлежит
2 0 0 Принадлежит
3 0 4 Принадлежит
4 5 0 Принадлежит
5 0 4.00001 Не принадлежит
6 -3 5 Не принадлежит
7 2 3 Принадлежит

Решение

Фигура в задаче представлена в виде двух четвертей окружностей, лежащих в I и IV четвертях с радиусами [latex] R1 [/latex] и [latex] R2 [/latex] , которые равны соответственно [latex] 4 [/latex] и [latex] 5 [/latex]. Центры окружностей находятся в начале координатных осей. Сразу после ввода координат точки выполняем проверку принадлежности фигуре, а именно: координата [latex]X\ge0[/latex] ? В случае отрицательного ответа программа выведет сообщение «Не принадлежит». Одновременно со знаком [latex]X[/latex] выполняется проверка с помощью формулы, полученной из уравнения окружности: [latex]{\left(x-{X}_{c}\right)}^{2}+{\left(y-{Y}_{c}\right)}^{2}\le{R}^{2}[/latex], где [latex]X_{c}[/latex] и [latex]Y_{c}[/latex] — координаты центра окружности. Если координаты точки проходят данную проверку для соответствующего радиуса, который зависит от знака [latex]Y[/latex], то точка принадлежит фигуре, в противном случае выведется сообщение «Не принадлежит».

Код

Код на сайте ideone.com находится здесь.

 

 

ML 9

Данная задача находится здесь.

Условие:

Определить периметр правильного [latex] m [/latex]-угольника, вписанного в окружность радиуса [latex] R [/latex].

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

Количество сторон правильного многоугольника [latex] m [/latex] и радиус [latex] R [/latex] описанной около него окружности.

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

Единственное число — периметр заданного многоугольника.

Тесты:

m R P
1 3 4 20.7846
2 6 5 30
3  8 13  79.5982
4 27 20 125.38

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

Код на сайте ideone.com можно получить здесь.

Убедиться в корректности формулы с помощью онлайн-калькулятора можно на этом сайте.

Решение:

Для решения данной задачи воспользуемся формулой для нахождения длины стороны правильного многоугольника с помощью радиуса описанной окружности: [latex]a=2\cdot R\cdot\sin{\frac{\pi}{m}}[/latex] , где [latex]R[/latex] — радиус описанной окружности, а [latex]m[/latex] — количество сторон правильного многоугольника. В задаче необходимо найти периметр, т.е. общую длину всех сторон: [latex]P=a\cdot m[/latex] . Таким образом, объединив формулы, получаем конечную формулу для нахождения периметра правильного многоугольника: [latex]P=\left(2\cdot R\cdot\sin{\frac{\pi}{m}}\right)\cdot m[/latex] , значение которой и необходимо вывести.

Источник формул : wikipedia.

 

 

ML8

Задача. Определить периметр правильного [latex]n[/latex]-угольника, описанного около окружности радиуса [latex]r[/latex].

Тесты

[latex]n[/latex] [latex]r[/latex] [latex]P[/latex]
4 2 16
3 5 51.9615
7 3 20.2261
5 5 36.3271
6 6 41.5692

Решение

Величину угла можно найти если задано только количество вершин — [latex]\frac{\pi\cdot(n-2))}{n}[/latex].

Для примера можно рассмотреть квадрат.
Без імені
Так как квадрат — правильный четырёхугольник, то центр вписанной окружности совпадает с центром описанной окружности.  [latex]R[/latex]  делит угол напополам — [latex]\frac{\alpha }{2}[/latex].  Отсюда получаем треугольник:

Без імені

[latex]\frac{\alpha }{2}[/latex] — половина угла квадрата, [latex]\frac{a}{2}[/latex] — половина стороны. Так как [latex]r[/latex] проходит перпендикулярно к стороне [latex]a[/latex], то мы можем воспользоваться формулой тангенса — [latex]tg\frac{\alpha }{2}=\frac{r}{0.5a}=\frac{2r}{a}[/latex] .

[latex]a=\frac{2r}{tg\frac{\alpha }{2}}[/latex].

Выводим формулу только с  [latex]n[/latex] и [latex]r[/latex].

[latex]P=\frac{2nr}{tg(\frac{\pi(n-2)}{2n})}[/latex].

Код

Код можно увидеть здесь