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

Задача

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

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

В первой строке находится количество синих квадратов $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$

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

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

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

Чтобы доказать это, пусть сторона квадрата равна $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

ML18

Задача ML18

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

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

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

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex],  значения которых не превышают по модулю [latex]100[/latex].

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

Вывести периметр [latex]p[/latex] данного треугольника.

Также условие задачи можно посмотреть здесь.

Тестирование

Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex]) Выходные данные
1 2 2 5 1  0 -1 3 5 10 16.0261556346
2 1 4 5 3 6 0 10.5 -2 -1 31.9047289894
3 15 26 13 32 18 56 80 0 -6.2 212.0962807371
4 -13 68 44 99 -100 70 0 2 1 450.5748518262
5 100 9 17 18 29 88 65 -16 0.36 310.4318979186

Реализация

Алгоритм решения

  1. Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
  2. Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
  3. Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

Подробнее о декартовой системе координат можно прочесть здесь.

Для запроса на выполнение следует перейти по ссылке.

 

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].

Код

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

 

А25а

Задача «Периметр треугольника». Произвольный треугольник задан координатами его вершин [latex]A[/latex],  [latex]B[/latex],  [latex]C[/latex]. Вычислите длины его сторон  [latex]|AB|[/latex],  [latex]|BC|[/latex],  [latex]|AC|[/latex], а также его периметр  [latex]p[/latex].

Для нахождения длин сторон используется формула расстояния между точками:

[latex]|AB|=\sqrt{\left(x_{A}-x_{B}\right)^{2}+\left(y_{A}-y_{B}\right)^{2}}[/latex],

[latex]|BC|=\sqrt{\left(x_B-x_C\right)^2+\left(y_B-y_C\right)^2}[/latex],

[latex]|AC|=\sqrt{\left(x_A-x_C\right)^2+\left(y_A-y_C\right)^2}[/latex],

периметр – это сумма длин сторон:

[latex]p=|AB|+|BC|+|AC|[/latex]

[latex]A[/latex] [latex]B[/latex] [latex]C[/latex] [latex]\left|AB\right|[/latex] [latex]\left|BC\right|[/latex] [latex]\left|AC\right|[/latex] [latex]p[/latex]  Комментарий
(0,0) (0,3) (4,0) 3 5 4 12 Пройден
(0,0) (0,1) (1,0) 1 [latex]\sqrt{2}\approx 1.414[/latex] 1 [latex]2+\sqrt{2}\approx 3.414[/latex] Пройден
(0,0) (0,1) (0,2) 1  1 2 4 Пройден

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

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

Программа протестирована в среде ideone.com и Virtual C. Пройден тест «Test Coding Rules» среды Virtual C на стиль написания кода. Для всех числовых значений в программе используется вещественный тип данных двойной точности. Исходные данные – координаты точек [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] – содержатся в переменных xA, yA, xB, yB, xC, xC, значения которых вводятся со стандартного потока ввода.

Проверить работу программы можно здесь.