e-olymp 124. Квадрат

08/12/2019 by Олег Сторожев

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

Найдите периметр и площадь квадрата.

Входные данные:
Каждая строка является отдельным тестом и содержит одно целое число — длину стороны квадрата $n$ (1 $\leqslant$ $n$ $\leqslant$ 1000).

Выходные данные:
Для каждого теста выведите в одной строке периметр и площадь квадрата.

Тесты

№	Входные данные	Выходные данные
1	3 5 10	12 9 20 25 40 100
2	3 3 3	12 9 12 9 12 9
3	1000 1 500	4000 1000000 4 1 2000 250000

Код

#include <iostream>
using namespace std;
int main() {
    int n,P,S;
    while (cin >> n) {
        P = 4*n; // считаем периметр квадрата
        S = n*n; // считаем площадь квадрата
        cout << P << " " << S << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,P,S;

while (cin >> n) {

P = 4*n; // считаем периметр квадрата

S = n*n; // считаем площадь квадрата

cout << P << " " << S << "\n";

}

return 0;

}

Решение

У нас дана сторона квадрата $n$.

Находим периметр квадрата, используя формулу $P = 4n$.
Находим площадь квадрата, используя формулу $S = n^{2}$.
Так как каждая новая строка — новое значение для стороны квадрата и таких строк неизвестное количество то используем while (cin >> n) для потоковой обработки данных.

Ссылки

Задача на сайте e-olymp
код решения Ideone

Олег Сторожев

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

Павел Жуков

ML18

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

Задача 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

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main ()
{
	double x1, x2, x3, y1, y2, y3, z1, z2, z3;
	long double a, b, c, p;
	//стороны AB, BC, AC треугольника ABC обозначим 
	//соответственно, используя переменные a, b, c
	//используем значения переменных с плавающей точкой
	cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;
	a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));
	b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));
	c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));
	p= a + b + c;
	//вычисляем периметр 
	cout << fixed << setprecision(10) << p << endl;
	//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой
	return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main ()

{

double x1, x2, x3, y1, y2, y3, z1, z2, z3;

long double a, b, c, p;

//стороны AB, BC, AC треугольника ABC обозначим

//соответственно, используя переменные a, b, c

//используем значения переменных с плавающей точкой

cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;

a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));

b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));

c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));

p= a + b + c;

//вычисляем периметр

cout << fixed << setprecision(10) << p << endl;

//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой

return 0;

}

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

Задан произвольный треугольник [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] соответственно.
Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[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].
Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

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

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

Кудымовская Вика

ML 9

23/09/2015 by Антон Локтев

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

Условие:

Определить периметр правильного [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

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){ 
	double m,R;
	cin >> m >> R;
	cout << 2*R*sin(M_PI/m)*m;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double m,R;

cin >> m >> R;

cout << 2*R*sin(M_PI/m)*m;

return 0;

}

Код на сайте 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.

Антон Локтев

www.e-olymp.com/ru/users/Antonio_L

ML8

23/09/2015 by Настя Ивасенко

Задача. Определить периметр правильного [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].

Код

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
	int n;
	double r;
	cin >> n >> r;
	cout << (2*n*r/tan(M_PI*(n-2)/(2*n))) << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

double r;

cin >> n >> r;

cout << (2*n*r/tan(M_PI*(n-2)/(2*n))) << endl;

return 0;

}

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

Настя Ивасенко

А25а

18/09/2014 by Антоненко Александр Сергеевич

Задача «Периметр треугольника». Произвольный треугольник задан координатами его вершин [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	Пройден

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

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

//Calculation of sides and perimeter of triangle
#include <stdio.h>
#include <math.h>

int main(void){
	double xA, yA, xB, yB, xC, yC, AB, BC, AC, p;
	printf("Coordinates of point A:\n");
	scanf("%lf %lf", &xA, &yA);
	printf("Coordinates of point B:\n");
	scanf("%lf %lf", &xB, &yB);
	printf("Coordinates of point C:\n");
	scanf("%lf %lf", &xC, &yC);
	AB = sqrt((xA - xB) * (xA - xB) + (yA - yB) * (yA - yB));
	BC = sqrt((xB - xC) * (xB - xC) + (yB - yC) * (yB - yC));
	AC = sqrt((xA - xC) * (xA - xC) + (yA - yC) * (yA - yC));
	p = AB + BC + AC;
	printf("AB=%8lg\n", AB);
	printf("BC=%8lg\n", BC);	
	printf("AC=%8lg\n", AC);	
	printf("p =%8lg\n", p);
	return 0;
}

//Calculation of sides and perimeter of triangle

#include <stdio.h>

#include <math.h>

int main(void){

double xA, yA, xB, yB, xC, yC, AB, BC, AC, p;

printf("Coordinates of point A:\n");

scanf("%lf %lf", &xA, &yA);

printf("Coordinates of point B:\n");

scanf("%lf %lf", &xB, &yB);

printf("Coordinates of point C:\n");

scanf("%lf %lf", &xC, &yC);

AB = sqrt((xA - xB) * (xA - xB) + (yA - yB) * (yA - yB));

BC = sqrt((xB - xC) * (xB - xC) + (yB - yC) * (yB - yC));

AC = sqrt((xA - xC) * (xA - xC) + (yA - yC) * (yA - yC));

p = AB + BC + AC;

printf("AB=%8lg\n", AB);

printf("BC=%8lg\n", BC);

printf("AC=%8lg\n", AC);

printf("p =%8lg\n", p);

return 0;

}

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

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