e-olymp 7612. Алекс и квадраты оригами

Задача

Алекс любит оригами — японское искусство складывания из бумаги. Большинство конструкций оригами начинаются с квадратного листа бумаги. Алекс собирается сделать подарок для своей матери. Подарочная конструкция требует три одинаковых квадратных листа бумаги, но у Алекса имеется только один прямоугольный лист. Он может из него вырезать квадраты, стороны которых должны быть параллельны сторонам листа. Помогите Алексу определить максимально возможный размер квадратов, который он способен вырезать.

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

В одной строке два целых числа [latex]h[/latex] и [latex]w[/latex] ([latex]1 ≤ h, w ≤ 1000[/latex]) — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex]h × w[/latex] так, чтобы их стороны были параллельны сторонам листа.

Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные Выходные данные
$100$ $100$ $50.000$
$10$ $80$ $10.000$
$50$ $76$ $25.333$
$60$ $27$ $20.000$
$8$ $3$ $2.667$

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

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

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за [latex]a[/latex] меньшую сторону листа бумаги, а за [latex]b[/latex] — большую. Если [latex]a[/latex] не больше [latex]\frac{b}{3}[/latex], то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги [latex]a[/latex]. В противном случае рассмотрим два варианта:

  1. Если [latex]\frac{a}{2}<\frac{b}{3}[/latex], то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число [latex]\frac{a}{2}[/latex].
  2. Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число [latex]\frac{b}{3}[/latex].

Таким образом, в случае [latex]a>\frac{b}{3}[/latex] ответом будет служить большее из двух чисел [latex]\frac{a}{2}[/latex] и [latex]\frac{b}{3}[/latex].
Минимальное из [latex]\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex] и [latex]a[/latex] число и будет ответом.
Проверим нашу формулу:если [latex]a<\frac{b}{3}[/latex], то [latex] \max\left(\frac{b}{3},\frac{a}{2}\right)=\frac{b}{3} [/latex], и тогда [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=a[/latex]. Иначе [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex], что нам и требуется.

Ссылки

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

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

Костя Григорян
Костя Григорян

Latest posts by Костя Григорян (see all)

Задача

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

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

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

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

Два числа, координаты искомой вершины прямоугольника. Все входные и выходные данные — целые числа, не превышающие по модулю [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
Код решения

Ю2.6

Условие

Четырёхугольник [latex]ABCD[/latex] задан координатами своих вершин на плоскости: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex] и [latex]C(x_c,y_c)[/latex], [latex]D(x_d,y_d)[/latex]. Определить тип четырёхугольника: прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Учесть погрешность вычислений.

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

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

В одной строке заданы 8 чисел [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] — координаты вершин четырёхугольника [latex]ABCD[/latex],  значения которых не превышают по модулю [latex]50[/latex].

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

  1. В первой строке вывести: «Тип четырёхугольника: «(без кавычек).
  2. Во второй строке вывести:  «Произвольный четырёхугольник» или «Прямоугольник» или «Параллелограмм» или «Трапеция»(без кавычек). Одно исключает другое.

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

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

Координаты [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] Вердикт (тип четырёхугольника)
1. -5 -4 -1 -2 -4 3 -1 -8 Параллелограмм
2.  -2 -3 7 3 -2 1 7 1  Трапеция
 3. 0 0 1 1 0 1 1 0  Прямоугольник
 4.  50 -20 3 -50 7 6 2 3  Произвольный четырёхугольник
5. 2 -3 -6 -1 4 7 6 3 Параллелограмм
6. 1 -5 6 20 2 0 13 -9 Произвольный четырёхугольник
7. 0 1 2 1 0 1 1 0 Параллелограмм
8. -6 0 6 0 1 5 -4 -8 Прямоугольник

Реализация

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

  1. Задан четырёхугольник [latex]ABCD[/latex] с такими координатами вершин: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex], [latex]C(x_c,y_c)[/latex] и [latex]D(x_d,y_d)[/latex]. В данной задаче будет уместным использование аппарата векторной алгебры.  Пусть стороны четырёхугольника — векторы.
  2. Очевидно, что для того, чтобы определить тип данного четырёхугольника, необходимо воспользоваться известными свойствами, а именно: свойствами прямоугольника, параллелограмма и трапеции. Так как в задаче используется аппарат векторной алгебры, обращаемся к таким свойствам векторов, как коллинеарность и равенство.
  3. Сразу же установим: является ли четырёхугольник трапецией. Проверим одну из двух пар сторон на параллельность. Для этого воспользуемся условием коллинеарности векторов на плоскости: [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}[/latex], если [latex]a_i, b_i\ne0[/latex].  Координаты векторов [latex]\vec{b}[/latex] и [latex]\vec{d}[/latex] должны быть пропорциональны, что означает, что соответствующие стороны параллельны. Следовательно, [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Или же координаты векторов [latex]\vec{a}[/latex] и [latex]\vec{c}[/latex] должны быть пропорциональны. Проверяем: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex]. Если условие не выполняется, четырёхугольник произвольный. Если, напротив, координаты хотя бы одной пары векторов пропорциональны, четырёхугольник является трапецией.
  4. Если четырёхугольник — параллелограмм, то обе пары его противоположных сторон параллельны. Проверим, выполняется ли: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex] и [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Если условие выполняется, то заданный четырёхугольник — параллелограмм.
  5. Частным случаем параллелограмма является прямоугольник. Диагонали [latex] AC, BD[/latex] обозначим как [latex] l, m[/latex] соответственно. Пусть [latex] l, m[/latex] — векторы.  Вычислим длины векторов [latex]\vec{l}[/latex], [latex]\vec{m}[/latex], пользуясь формулой.  Получаем: [latex]\vec{|l|}= \sqrt{(x_c — x_a)\cdot (x_c -x_a) + (y_c — y_a)\cdot (y_c -y_a)}[/latex], [latex]\vec{|m|}= \sqrt{(x_d — x_b)\cdot (x_d -x_b) + (y_d — y_b)\cdot (y_d -y_b)}[/latex]. При условии, что [latex]\vec{l}=\vec{m}[/latex], имеем прямоугольник.

Более детально со свойствами и видами четырёхугольников можно ознакомиться здесь, а с основными сведениями из векторной алгебры — здесь.

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

 

 

А55

Кваша Дар`я Михайлівна
Кваша Дар`я Михайлівна

Latest posts by Кваша Дар`я Михайлівна (see all)

Задача. Даны действительные положительные числа [latex]a, b, c, d[/latex]. Выяснить, можно ли прямоугольник со сторонами [latex]a, b[/latex] уместить внутри прямоугольника со сторонами [latex]c, d [/latex] так, чтобы каждая из сторон одного прямоугольника была параллельна или перпендикулярна каждой из сторон второго прямоугольника.

Тесты:

c d a b Результат Комментарий
4 6 5 5 Нельзя разместить Пройден
4 8 7 3 Можно разместить Пройден
23 45 87 23 Нельзя разместить Пройден
15 33 15 12 Можно разместить Пройден
7 9 7 13 Нельзя разместить Пройден

Код на С

Код на Java

 

Решение: Прямоугольник можно разместить внутри другого если,  стороны меньше соответствующих им параллельным.  Согласно условию существует две различные комбинации размещения прямоугольника. Проверив необходимые неравенства, определим можно или нельзя разместить прямоугольник внутри другого.

Ознакомиться с кодом на С можно здесь, а с кодом на Java здесь.

Ю2.12

Бровко Ілля
Бровко Ілля

Latest posts by Бровко Ілля (see all)

Задача

Планировка. Можно ли на прямоугольном участке застройки размером a на b метров разместить два дома размером в плане p на q и r на s метров? Дома можно располагать только параллельно  сторонам участка.

Ниже представлены одни из возможных вариантов расположения домов на участке:

Илья_задание_01 Илья_задание_04

a b p q r s Ответ
100 150 20 70 25 50 Дома могут быть построены на заданном участке.
20 50 10 60 10 15 Дома не могут быть построены.
50 150 25 150 25 150 Дома могут быть построены на заданном участке.
50 150 50 75 50 75 Дома могут быть построены на заданном участке.
200 300 115 50 110 100 Дома могут быть построены на заданном участке.
2 4 1 3 2 2 Дома не могут быть построены.
2 5 1 3 2 3 Дома не могут быть построены.
2 5 2 2 1 4 Дома не могут быть построены.
3 3 2 2 2 2 Дома не могут быть построены.
2 10 10 1 10 1 Дома могут быть построены на заданном участке при повороте на 90 градусов.
10 2 1 10 1 10 Дома могут быть построены на заданном участке при повороте на 90 градусов.
2 10 1 10 10 1 Дома могут быть построены на заданном участке при повороте дома со сторонами r s на 90 градусов.
10 2 10 1 1 10 Дома могут быть построены на заданном участке при повороте дома со сторонами r s на 90 градусов.
10 2 1 10 10 1 Дома могут быть построены на заданном участке при повороте дома со сторонами p q на 90 градусов.
2 10 10 1 1 10 Дома могут быть построены на заданном участке при повороте дома со сторонами p q на 90 градусов.
2 3 1 1 2 3 Дома не могут быть построены.
2 4 1 1 3 3 Дома не могут быть построены.
2 6 1 3 3 3 Дома не могут быть построены.

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

Всего у нас есть 8 вариантов расположения домов на участке.

Каждый дом можно расположить на участке двумя способами (вертикально или горизонтально). Значит всего четыре различные комбинации их расположения относительно участка. Среди этих четырёх комбинация должна существовать по крайней мере одна в которой дома помещаются. Т.е. либо суммарная ширина домов меньше ширины участка и длина каждого дома меньше его длины, либо суммарная длина домов меньше длины участка и ширина каждого дома меньше ширины участка. Поскольку выполнится должно хоть одно такое условие, то их нужно соединить логическим “или”.

Так же у нас есть 4 различных комбинации размещения домов, в которых один из домов(а может и сразу два) не помещается на участке, но если его развернуть на [latex]90^{\circ}[/latex], то дома успешно разместятся на участке.

Ниже представлен сам код(C++):

Код на Java:

 

Ознакомится с программой можно тут (C++)/тут (Java).

Ю2.11

Задача жестянщика. Можно ли из круглой заготовки радиусом  [latex]r[/latex] вырезать две прямоугольные пластинки с размерами  [latex] a[/latex] × [latex] b[/latex] и [latex] c[/latex] × [latex]d[/latex]?

1.6 3 0 3 0 We can
1.6 3 1 3 1 We can’t
  2  3 1 3 1 We can
  2  5 1 4 1 We can’t
 

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

Безымянный

Можно заметить, что [latex] h=d1[/latex] (длина до центра окружности) — это катет прямоугольного треугольника, значит его можно найти по теореме Пифагора , зная радиус круга [latex] R[/latex]  и катит [latex] r[/latex] (в нашем случае [latex] a/2[/latex]) [latex] h=\sqrt{R^2-r^2}[/latex]). Вычитая из полученного [latex] h=d1[/latex]  ширину [latex] b[/latex] мы получим  сколько он места занимает при данной длине и ширине относительно центра круга. (Если у нас  [latex] b<d1[/latex], то для второго прямоугольника у нас будет больше места) Тоже самое мы проделываем и для второго прямоугольника и получаем наше [latex] h2=d2[/latex]. Дальше размещаем наши прямоугольники параллельно друг другу и смотрим, хватает ли места второму прямоугольнику места с учетом его ширины (Если по ширине второй прямоугольник не превышает оставшегося места) [latex]d<d2+(d1-b)[/latex].

 

Реализация на Java:

 

Ссылка на код программы.