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

Задача

На плоскости задано [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

 

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [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. Вписанные треугольники

Задача

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

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

Задача

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

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

Задано стороны [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

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

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

Дано

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

Цель

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

Идея

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

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

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

Ссылки

Задача на e-olymp

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

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

Задача

В белом квадрате [latex]N[/latex] раз выполнили одну и ту же операцию: один из наименьших белых квадратов разбили на 4 одинаковых квадрата и из них закрасили черным цветом. Для данного [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

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

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

При [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г

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