e-olymp 4720. Новая игра Серёжи

22/12/2020 by Кулік Віталій

Задача

Троечник Серёжа часто просит отличника Васю сделать ему домашнее задание. Так как при всей гениальности Васи он всё же не может справиться с работой мгновенно, то Серёже приходится ждать. Серёже скучно ждать долго без дела. Не так давно он придумал новую игру, чтобы скоротать время.

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

Помогите Серёже понять, расстроится он или нет.

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

Сначала с клавиатуры вводятся координаты левого верхнего угла чёрного прямоугольника, затем правого нижнего, затем координаты углов белого прямоугольника в том же формате и в конце — координаты точки. Все координаты — целые числа, по модулю не превышающие $10000$.

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

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

Тесты

№	Входные данные	Выходные данные
1	2 10 5 3 4 4 6 1 2 9	HAPPY
2	2 10 5 3 4 4 6 1 6 3	SAD
3	0 0 0 0 1 1 1 1 0 0	HAPPY
4	1 3 3 1 2 3 4 1 3 2	SAD
5	1 3 3 1 2 3 4 1 2 2	HAPPY

Код

#include <iostream>
using namespace std;

struct dot
{
    int x, y;
    dot(){
        cin >> x >> y;
    }
};
struct square
{
    dot upper_left, lower_right;
    bool is_point_on(dot &p) const
    {
        return p.x < lower_right.x and p.x > upper_left.x and p.y < upper_left.y and p.y > lower_right.y;
    }
    bool is_point_in(dot &p) const
    {
        return p.x <= lower_right.x and p.x >= upper_left.x and p.y <= upper_left.y and p.y >= lower_right.y;
    }
};

int main() {
    square black, white;
    dot point;
    cout << ((black.is_point_in(point) and not white.is_point_on(point))?"HAPPY":"SAD");
}

#include <iostream>

using namespace std;

struct dot

{

int x, y;

dot(){

cin >> x >> y;

}

};

struct square

{

dot upper_left, lower_right;

bool is_point_on(dot &p) const

{

return p.x < lower_right.x and p.x > upper_left.x and p.y < upper_left.y and p.y > lower_right.y;

}

bool is_point_in(dot &p) const

{

return p.x <= lower_right.x and p.x >= upper_left.x and p.y <= upper_left.y and p.y >= lower_right.y;

}

};

int main() {

square black, white;

dot point;

cout << ((black.is_point_in(point) and not white.is_point_on(point))?"HAPPY":"SAD");

}

Сокращенный код

#include <iostream>
using namespace std;

int main() {
    int bl_up_x, bl_up_y, bl_dw_x, bl_dw_y;
    int wh_up_x, wh_up_y, wh_dw_x, wh_dw_y;
    int p_x, p_y;
    cin >> bl_up_x >> bl_up_y >> bl_dw_x >> bl_dw_y;
    cin >> wh_up_x >> wh_up_y >> wh_dw_x >> wh_dw_y;
    cin >> p_x >> p_y;
    bool is_in_black = p_x <= bl_dw_x and p_x >= bl_up_x and p_y <= bl_up_y and p_y >= bl_dw_y;
    bool is_in_white = p_x < wh_dw_x and p_x > wh_up_x and p_y < wh_up_y and p_y > wh_dw_y;
    cout << (is_in_black and not is_in_white ? "HAPPY" : "SAD");
}

#include <iostream>

using namespace std;

int main() {

int bl_up_x, bl_up_y, bl_dw_x, bl_dw_y;

int wh_up_x, wh_up_y, wh_dw_x, wh_dw_y;

int p_x, p_y;

cin >> bl_up_x >> bl_up_y >> bl_dw_x >> bl_dw_y;

cin >> wh_up_x >> wh_up_y >> wh_dw_x >> wh_dw_y;

cin >> p_x >> p_y;

bool is_in_black = p_x <= bl_dw_x and p_x >= bl_up_x and p_y <= bl_up_y and p_y >= bl_dw_y;

bool is_in_white = p_x < wh_dw_x and p_x > wh_up_x and p_y < wh_up_y and p_y > wh_dw_y;

cout << (is_in_black and not is_in_white ? "HAPPY" : "SAD");

}

Решение

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

Ссылки

Задача на e-olymp
Код решения на ideone
Код сокращенного решения на ideone
Засчитанное решение на e-olymp

Related Images:

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

15/12/2018 by Александр Колаев

Задача

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

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

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

Решение

#include <iostream>;
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << (a + b) * 2;
    return 0;
}

#include <iostream>;

using namespace std;

int main() {

int a, b;

cin >> a >> b;

cout << (a + b) * 2;

return 0;

}

Объяснение

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

e-olymp
Запустить код на выполнение можно здесь

Related Images:

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

30/06/2018 by Павел Жуков

Задача

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

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

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

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

#include <iostream>
using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i){ int x, y; cin >> x >> y;
        squares[x + MAX_PAGE_SIZE / 2][y + MAX_PAGE_SIZE / 2] = 1;
    }
    int perimiter = 0;
    for (int i = 0; i < MAX_PAGE_SIZE; ++i){
        for (int j = 0; j < MAX_PAGE_SIZE; ++j){
            if (squares[i][j]){
                perimiter += !squares[i + 1][j] + !squares[i - 1][j] + !squares[i][j + 1] + !squares[i][j - 1];
            }
        }
    }
    int max = 0;
    for (int j = 1; (perimiter - 2 * j) / 2 > 0; ++j){ 
        int i = (perimiter - 2 * j) / 2; 
        if (i * j - n > max) {
            max = i * j - n;
        }
    }
    cout << max;
    return 0;
}

#include <iostream>

using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {

int n;

cin >> n;

for (int i = 0; i < n; ++i){ int x, y; cin >> x >> y;

squares[x + MAX_PAGE_SIZE / 2][y + MAX_PAGE_SIZE / 2] = 1;

}

int perimiter = 0;

for (int i = 0; i < MAX_PAGE_SIZE; ++i){

for (int j = 0; j < MAX_PAGE_SIZE; ++j){

if (squares[i][j]){

perimiter += !squares[i + 1][j] + !squares[i - 1][j] + !squares[i][j + 1] + !squares[i][j - 1];

}

int max = 0;

for (int j = 1; (perimiter - 2 * j) / 2 > 0; ++j){

int i = (perimiter - 2 * j) / 2;

if (i * j - n > max) {

max = i * j - n;

}

cout << max;

return 0;

}

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

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

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

Related Images:

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

23/12/2017 by Даниил Крутоголов

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

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

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

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

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

#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int a, b;

cin >> a >> b;

cout << a * b << endl;

return 0;

}

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

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

Ссылки

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

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

Related Images:

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

06/12/2017 by Александра Рябова

Задача

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

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

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

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

#include<iostream>
#include<cmath>
#include <iomanip>
using namespace std;

int main()
{
    cout.precision(4);
    double h, w = 0;
    cin >> h;
    cin >> w;
    double b = max(h, w);
    double a = min(w, h);
    double c = min(a, max(b/3, a/2));
    cout << fixed << c;
}

#include<iostream>

#include<cmath>

#include <iomanip>

using namespace std;

int main()

{

cout.precision(4);

double h, w = 0;

cin >> h;

cin >> w;

double b = max(h, w);

double a = min(w, h);

double c = min(a, max(b/3, a/2));

cout << fixed << c;

}

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

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

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

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

Если [latex]\frac{a}{2}<\frac{b}{3}[/latex], то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число [latex]\frac{a}{2}[/latex].
Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число [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
Код решения задачи

Related Images:

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

04/12/2017 by Костя Григорян

Задача №130 (дубль — №7379)

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

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

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

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

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

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

#include <iostream>
using namespace std;

int main() {
    int x1, x2, x3, y1, y2, y3;
    cin  >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0)
    {
        cout << x2+x3-x1 << " " << y2+y3-y1;
    }
    else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0)
    {
        cout << x1+x3-x2 << " " << y1+y3-y2;
    }
    else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0)
    {
        cout << x1+x2-x3 << " " << y1+y2-y3;
    }   
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x1, x2, x3, y1, y2, y3;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0)

{

cout << x2+x3-x1 << " " << y2+y3-y1;

}

else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0)

{

cout << x1+x3-x2 << " " << y1+y3-y2;

}

else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0)

{

cout << x1+x2-x3 << " " << y1+y2-y3;

}

return 0;

}

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

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

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [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
Код решения

Related Images:

Ю2.6

30/09/2015 by Кудымовская Вика

Условие

Четырёхугольник [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].

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

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

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

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

№	Координаты [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	Прямоугольник

Реализация

#include <iostream>
#include <cmath>
using namespace std;
 
int main () {
    setlocale(LC_ALL,"Russian");
    int xa, xb, xc, xd, ya, yb, yc, yd; 
    cout << "Тип четырёхугольника: " << endl;
    cin >> xa >> xb >> xc >> xd >> ya >> yb >> yc >> yd;
    //диагонали AC и BD четырёхугольника ABCD обозначим, как l и m, они являются векторами
    long double l= abs(sqrt((xc - xa) * (xc - xa) + (yc - ya) * (yc -ya)));
    long double m= abs(sqrt((xd - xb) * (xd - xb) + (yd - yb) * (yd -yb)));
    if (((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)) || ((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya))) { 
        if (((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya)) && ((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb))) 
            if (l==m)
                cout << "Прямоугольник" << endl;
            else {
                cout << "Параллелограмм" << endl;
            }
        else {
            cout << "Трапеция" << endl;
        }
    }
    else {
        cout << "Произвольный четырехугольник" << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main () {

setlocale(LC_ALL,"Russian");

int xa, xb, xc, xd, ya, yb, yc, yd;

cout << "Тип четырёхугольника: " << endl;

cin >> xa >> xb >> xc >> xd >> ya >> yb >> yc >> yd;

//диагонали AC и BD четырёхугольника ABCD обозначим, как l и m, они являются векторами

long double l= abs(sqrt((xc - xa) * (xc - xa) + (yc - ya) * (yc -ya)));

long double m= abs(sqrt((xd - xb) * (xd - xb) + (yd - yb) * (yd -yb)));

if (((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)) || ((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya))) {

if (((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya)) && ((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)))

if (l==m)

cout << "Прямоугольник" << endl;

else {

cout << "Параллелограмм" << endl;

}

else {

cout << "Трапеция" << endl;

}

else {

cout << "Произвольный четырехугольник" << endl;

}

return 0;

}

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

Задан четырёхугольник [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]. В данной задаче будет уместным использование аппарата векторной алгебры. Пусть стороны четырёхугольника — векторы.
Очевидно, что для того, чтобы определить тип данного четырёхугольника, необходимо воспользоваться известными свойствами, а именно: свойствами прямоугольника, параллелограмма и трапеции. Так как в задаче используется аппарат векторной алгебры, обращаемся к таким свойствам векторов, как коллинеарность и равенство.
Сразу же установим: является ли четырёхугольник трапецией. Проверим одну из двух пар сторон на параллельность. Для этого воспользуемся условием коллинеарности векторов на плоскости: [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]. Если условие не выполняется, четырёхугольник произвольный. Если, напротив, координаты хотя бы одной пары векторов пропорциональны, четырёхугольник является трапецией.
Если четырёхугольник — параллелограмм, то обе пары его противоположных сторон параллельны. Проверим, выполняется ли: [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]. Если условие выполняется, то заданный четырёхугольник — параллелограмм.
Частным случаем параллелограмма является прямоугольник. Диагонали [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], имеем прямоугольник.

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

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

Related Images:

А55

28/09/2014 by Кваша Дар`я Михайлівна

Задача. Даны действительные положительные числа [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	Нельзя разместить	Пройден

Код на С

#include <stdio.h>
 
int main(void) 
{
	double a,b,c,d;
	scanf("%lf %lf %lf %lf", &c, &d, &a, &b);
	if (((a<d)&&(b<c))||((a<c)&&(b<d))) printf("Можно разместить");
	else printf("Нельзя разместить");
	return 0;
}
<strong> </strong>

#include <stdio.h>

int main(void)

{

double a,b,c,d;

scanf("%lf %lf %lf %lf", &c, &d, &a, &b);

if (((a<d)&&(b<c))||((a<c)&&(b<d))) printf("Можно разместить");

else printf("Нельзя разместить");

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;


class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
	 Scanner in=new Scanner(System.in);	
	 double a,b,c,d;
	 c=in.nextDouble();
	 d=in.nextDouble();
	 a=in.nextDouble();
	 b=in.nextDouble();
	 if (((a<d)&&(b<c))||((a<c)&&(b<d)))  System.out.print("Можно разместить");
	 else  System.out.print("Нельзя разместить");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in=new Scanner(System.in);

double a,b,c,d;

c=in.nextDouble();

d=in.nextDouble();

a=in.nextDouble();

b=in.nextDouble();

if (((a<d)&&(b<c))||((a<c)&&(b<d))) System.out.print("Можно разместить");

else System.out.print("Нельзя разместить");

}

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

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

Related Images:

Ю2.12

24/09/2014 by Бровко Ілля

Задача

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

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

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++):

#include <stdio.h>
 
int main(void) 
{
	double a, b, p, q, r, s;
	scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &p, &q, &r, &s);
   	printf(
   		(a >= p && a >= r && b >= (q + s)) || // Дома стоят вдоль b (4 варианта)
   		(a >= q && a >= r && b >= (p + s)) ||
   		(a >= p && a >= s && b >= (q + r)) ||
   		(a >= q && a >= s && b >= (p + r)) ||
   		(b >= p && b >= r && a >= (q + s)) || // Дома стоят вдоль a (4 варианта)
   		(b >= q && b >= r && a >= (p + s)) ||
   		(b >= p && b >= s && a >= (q + r)) ||
   		(b >= q && b >= s && a >= (p + r)) ? "Могут" : "Нет\n");
}

#include <stdio.h>

int main(void)

{

double a, b, p, q, r, s;

scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &p, &q, &r, &s);

printf(

(a >= p && a >= r && b >= (q + s)) || // Дома стоят вдоль b (4 варианта)

(a >= q && a >= r && b >= (p + s)) ||

(a >= p && a >= s && b >= (q + r)) ||

(a >= q && a >= s && b >= (p + r)) ||

(b >= p && b >= r && a >= (q + s)) || // Дома стоят вдоль a (4 варианта)

(b >= q && b >= r && a >= (p + s)) ||

(b >= p && b >= s && a >= (q + r)) ||

(b >= q && b >= s && a >= (p + r)) ? "Могут" : "Нет\n");

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Brovko
{
	public static void main (String[] args) throws java.lang.Exception
	{
	double a, b, p, q, r, s;
	Scanner in = new Scanner(System.in);
	a=in.nextDouble();
	b=in.nextDouble();
	p=in.nextDouble();
	q=in.nextDouble();
	r=in.nextDouble();
	s=in.nextDouble();
   	System.out.printf(
   		(a >= p && a >= r && b >= (q + s)) || // Дома стоят вдоль b (4 варианта)
   		(a >= q && a >= r && b >= (p + s)) ||
   		(a >= p && a >= s && b >= (q + r)) ||
   		(a >= q && a >= s && b >= (p + r)) ||
   		(b >= p && b >= r && a >= (q + s)) || // Дома стоят вдоль a (4 варианта)
   		(b >= q && b >= r && a >= (p + s)) ||
   		(b >= p && b >= s && a >= (q + r)) ||
   		(b >= q && b >= s && a >= (p + r)) ? "Yes" : "No\n");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Brovko

{

public static void main (String[] args) throws java.lang.Exception

{

double a, b, p, q, r, s;

Scanner in = new Scanner(System.in);

a=in.nextDouble();

b=in.nextDouble();

p=in.nextDouble();

q=in.nextDouble();

r=in.nextDouble();

s=in.nextDouble();

System.out.printf(

(a >= p && a >= r && b >= (q + s)) || // Дома стоят вдоль b (4 варианта)

(a >= q && a >= r && b >= (p + s)) ||

(a >= p && a >= s && b >= (q + r)) ||

(a >= q && a >= s && b >= (p + r)) ||

(b >= p && b >= r && a >= (q + s)) || // Дома стоят вдоль a (4 варианта)

(b >= q && b >= r && a >= (p + s)) ||

(b >= p && b >= s && a >= (q + r)) ||

(b >= q && b >= s && a >= (p + r)) ? "Yes" : "No\n");

}

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

Related Images:

Ю2.11

19/09/2014 by Осецимський Анатолій Вадимович

Задача жестянщика. Можно ли из круглой заготовки радиусом [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

#include <iostream>
#include <math.h>
using namespace std;

double sort(double a,double b) //ссортировка сторон прямоугольника на длину и ширину
{
	double q;
	if (b>a)
	{
		q=b;
		a=b;
		a=q;
	}
	return a,b;
}

int main() {
	float r,a,b,c,d,q;//вводим переменные для входных данных
	float d1,d2;//переменные для определения длинны до центра круга при радиусе r
	scanf("%f %f %f %f %f", &r , &a , &b , &c , &d );
	sort(a,b);sort(c,d);
	if ((a<r*2) && (c<r*2))//проверка не больше ли стороны ,чем диаметр
		{
			d1 = sqrt(r*r-(a/2)*(a/2));//ищем расстояние до центра от середины длины первого прямоугольника
			d2 = sqrt(r*r-(c/2)*(c/2));//ищем расстояние до центра от середины длины второго прямоугольника
			if (d < d2+(d1-b))//если ширина второго прямоугольника меньше суммы его длинны до центра круга и разности длинны до центра первого прямоугольник с его шириной(Если ширина первого прямоугольника  больше его длинны до центра,то для ширины второго будет меньше места,это понятно)
				{
					printf("We can");
				}
				else
				{
					printf("We can't");
				}
		}
		else
		{
			printf("We can't!");
		}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double sort(double a,double b) //ссортировка сторон прямоугольника на длину и ширину

{

double q;

if (b>a)

{

q=b;

a=b;

a=q;

}

return a,b;

}

int main() {

float r,a,b,c,d,q;//вводим переменные для входных данных

float d1,d2;//переменные для определения длинны до центра круга при радиусе r

scanf("%f %f %f %f %f", &r , &a , &b , &c , &d );

sort(a,b);sort(c,d);

if ((a<r*2) && (c<r*2))//проверка не больше ли стороны ,чем диаметр

{

d1 = sqrt(r*r-(a/2)*(a/2));//ищем расстояние до центра от середины длины первого прямоугольника

d2 = sqrt(r*r-(c/2)*(c/2));//ищем расстояние до центра от середины длины второго прямоугольника

if (d < d2+(d1-b))//если ширина второго прямоугольника меньше суммы его длинны до центра круга и разности длинны до центра первого прямоугольник с его шириной(Если ширина первого прямоугольника больше его длинны до центра,то для ширины второго будет меньше места,это понятно)

{

printf("We can");

}

else

{

printf("We can't");

}

else

{

printf("We can't!");

}

return 0;

}

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

Можно заметить, что [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:

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone{
	
	static void swap(double a, double b){
		if(b > a){
			double q = a;
			a = b;
			b = q;
		}
	}
	
	public static void main (String[] args)	{
		double d1, d2;//переменные для определения длинны до центра круга при радиусе r
		Scanner in = new Scanner(System.in);
		double r = in.nextDouble();
		double a = in.nextDouble();
		double b = in.nextDouble();
		double c = in.nextDouble();
		double d = in.nextDouble();
		swap(a, b);swap(c, d);
		if ((a < r*2) && (c < r*2)){
			d1 = Math.sqrt(r*r-(a/2)*(a/2));//ищем расстояние до центра от середины длины первого прямоугольника
			d2 = Math.sqrt(r*r-(c/2)*(c/2));//ищем расстояние до центра от середины длины второго прямоугольника
			if (d < d2 + (d1 -  b)){
					System.out.println("We can");
				}
				else{
					System.out.println("We can't");
				}
		}
		else{
			System.out.println("We can't!");
		}
	}
}