e-olymp 1509. Раздел королевства.

25/12/2018 by Виктор Иванов

Задача

Король страны Геометрии в заботах. У него есть три сына, которые постоянно ссорятся. Король применял разные методы примерения, но все напрасно. И это его очень беспокоило.

«А что если разделить королевство?» подумал король. Он пригласил советников и описал свой план. Король открыл карту.

Королевство имеет форму треугольника с вершинами [latex]A, B, C[/latex]. Король провел линию от [latex]B[/latex] к [latex]E[/latex] ([latex]E[/latex] — произвольная точка на отрезке [latex]AC[/latex]) и линию от [latex]C[/latex] к [latex]F [/latex]([latex]F[/latex] — произвольная точка на отрезке [latex]AB[/latex]). Пересечение [latex]BE[/latex] и [latex]CF[/latex] обозначено через [latex]X[/latex].

Теперь образовалось четыре части — [latex]a[/latex] (треугольник [latex]BFX[/latex]), [latex]b[/latex] (треугольник [latex]BCX[/latex]), [latex]c[/latex] (треугольник [latex]CEX[/latex]) и [latex]d[/latex] (четырехугольник [latex]AEXF[/latex]). Король решил отдать области[latex] a[/latex], [latex]b[/latex], [latex]c[/latex] трем сыновьям. А область [latex]d[/latex] станет новым королевством.

Вы — главный советник. Король сообщает Вам значения [latex]a, b, c[/latex]. Вам необходимо найти значение [latex]d[/latex]. Если его найти невозможно, то сообщить об этом.

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

Состоит из не более чем [latex]1000[/latex] тестов. Каждый тест содержит три неотрицательных действительных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] (разделенных пробелом). Входные данные заканчиваются тестом у которого [latex]a = -1[/latex] и он не обрабатывается.

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

Для каждого теста вывести его номер, начиная с [latex]1[/latex]. В следующей строке вывести [latex]d[/latex] (величина области королевства после раздела) округленное до [latex]4[/latex] десятичных знаков или ‘Poor King!’ (без кавычек) если значение [latex]d[/latex] определить невозможно. Формат выходных данных показан в примере.

Тесты

№	Входные данные	Выходные данные
1	1 2 1	Set 1: 2.0000
2	2 4 2	Set 2: 4.0000
3	1 3 3	Set 3: 5.0000
4	-1 0 0

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

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

int main () {
    double a, b, c, d, d1, d2;
    int l = 0;
    while (cin >> a >> b >> c && a!= -1.0) {
        d1 = a * c / b;
        l++;
        if (b > d1) {
            d2 = (c + d1) * (a + d1) / (b - d1);
            cout << fixed << setprecision(4) << "Set" << " " << l << ':' << endl;
            cout << d1 + d2<< endl;
        }
        else cout << "Set" << " " << l << ':' << endl << "Poor King!" << endl;
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main () {

double a, b, c, d, d1, d2;

int l = 0;

while (cin >> a >> b >> c && a!= -1.0) {

d1 = a * c / b;

l++;

if (b > d1) {

d2 = (c + d1) * (a + d1) / (b - d1);

cout << fixed << setprecision(4) << "Set" << " " << l << ':' << endl;

cout << d1 + d2<< endl;

}

else cout << "Set" << " " << l << ':' << endl << "Poor King!" << endl;

}

return 0;

}

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

Для решения задачи соединим точки [latex]F[/latex] и [latex]E[/latex] линией. Получили два треугольника: [latex]d1[/latex] и [latex]d2[/latex]. Искомую площадь [latex]d[/latex] будем искать как сумму площадей [latex]d1[/latex] и [latex]d2[/latex]. Треугольники [latex]BFO[/latex] и [latex]EFO[/latex] имеют общее основание [latex]FO[/latex]. Следовательно их площади [latex]d1[/latex] и [latex]a[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]FO[/latex]. Аналогично треугольники [latex]BCO[/latex] и [latex]ECO[/latex] имеют общее основание [latex]OF[/latex]. Значит их площади [latex]c[/latex] и [latex]b[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]CO[/latex]. То есть $\frac{d_1}{a}=\frac{c}{b}$. Отсюда $d_1=\frac{ac}{b}$. Теперь рассмотрим треугольники [latex]CAF[/latex] и [latex]CBF[/latex] с основаниями [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]С[/latex] на прямую [latex]AB[/latex]. Следовательно площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Аналогично треугольники [latex]EAF[/latex] и [latex]EBF[/latex] имеют основания [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]E[/latex] на прямую [latex]AB[/latex]. Площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Тогда $$\frac{AF}{BF}=\frac{S_{\blacktriangle} CAF}{S\blacktriangle CBF}=\frac{c+d_1+d_2}{a+b}$$. $$\frac{AF}{BF}=\frac{S\blacktriangle EAF}{S\blacktriangle EBF}=\frac{d_2}{a+d_1}$$. Следовательно $\frac{c+d_1+d_2}{a+b}=\frac{d_2}{a+d_1}$. Поскольку [latex]d1[/latex] уже найдено, то имеем равенство с одним неизвестным [latex]d2[/latex] : $$d_2=\frac{(c+d_1)(a+d_1)}{b-d_1}$$. Если [latex]b \leqslant d1[/latex], то решения не существует.

Ссылки

Условие задачи на e-olymp
Код программы на ideone

Related Images:

e-olymp 2612. Разрезание на квадраты

14/12/2017 by Александр Волынец

Задача

Полоска бумаги имеет размеры [latex]A×B[/latex]. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?

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

Программе даны числа [latex]A[/latex] и [latex]B[/latex] [latex](1 ≤ A, B ≤ 10^9).[/latex]

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

Требуется вывести количество квадратов.

Тесты

Входные данные	Выходные данные
12 4	3
15 3	5
20 20	1
8 12	3

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

#include <iostream>
using namespace std;

int main() {
    int a, b, temp = 0;
    bool need = 1;
    cin >> a >> b;
    while (need) {
        if (a >= b) {
            temp = temp + a / b;
            a = a%b;
        }
        else
        {
            temp = temp + b / a;
            b = b%a;
        }
        if (a == 0 || b == 0) {
            need = 0;
        }
    }
    cout << temp;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, temp = 0;

bool need = 1;

cin >> a >> b;

while (need) {

if (a >= b) {

temp = temp + a / b;

a = a%b;

}

else

{

temp = temp + b / a;

b = b%a;

}

if (a == 0 || b == 0) {

need = 0;

}

cout << temp;

return 0;

}

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

Нам было дана высота и ширина полоски бумаги. Есть три варианта:

Высота равна ширине
Высота больше ширины
Высота меньше ширины

В первом случае нам надо вывести на экран единицу. Во втором случаем начинаем вычитать a - b до того момента, как a не будет меньше b или a не будет равняться 0. В третьем случае начинаем вычитать b - a до того момента, как b не будет меньше a или b не будет равняться 0.

Ссылки

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

Related Images:

e-olymp 932. Высота треугольника

04/12/2017 by Валерия Ларикова

Задача

Определить высоту треугольника площадью [latex]S[/latex], если его основание больше высоты на величину [latex]a[/latex].

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

Два целых числа: [latex]S (0 < S ≤ 100), и[/latex] [latex]a[/latex] ([latex]\left | a \right |[/latex] ≤ 100).

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

Искомая высота с точностью до сотых.

Тесты

#	Входные данные	Выходные данные
1	20 7	3.73
2	35 3	7.00
3	12 4	3.29
4	67 9	7.92
5	135 13	11.17

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

#include <iostream>
#include <cmath>//данная библиотека позволяет извлекать корень квадратный
#include <iomanip>//данная библиотека позволяет устанавливать количество знаков после запятой
using namespace std;
 
int main() {
    int s, a;//площадь треугольника,разность основания и высоты 
    int d;//дискриминант 
    double h, dk;// высота треугольника, корень квадратный из дискриминанта  
    cin >> s >> a; 
    d = a*a + 8*s;//формула для нахождения дискриминанта 
    dk = sqrt(d);//извлекаем корень квадратный из дискриминанта 
    h = (-a + dk)/2;//формула для нахождения высоты треугольника
    cout << fixed << setprecision(2) << h;// функция с её аргументом позволяет вывеси результат, округлённый до двух десятичных знаков
 
    return 0;
}

#include <iostream>

#include <cmath>//данная библиотека позволяет извлекать корень квадратный

#include <iomanip>//данная библиотека позволяет устанавливать количество знаков после запятой

using namespace std;

int main() {

int s, a;//площадь треугольника,разность основания и высоты

int d;//дискриминант

double h, dk;// высота треугольника, корень квадратный из дискриминанта

cin >> s >> a;

d = a*a + 8*s;//формула для нахождения дискриминанта

dk = sqrt(d);//извлекаем корень квадратный из дискриминанта

h = (-a + dk)/2;//формула для нахождения высоты треугольника

cout << fixed << setprecision(2) << h;// функция с её аргументом позволяет вывеси результат, округлённый до двух десятичных знаков

return 0;

}

Алгоритм решения задачи

Формула для вычисления площади треугольника [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot c[/latex], где [latex]h[/latex] – высота, а [latex]c[/latex] – сторона, к которой высота проведена.
В задаче сказано, что основание больше высоты на величину [latex]a[/latex]. Значит вместо [latex]c[/latex] мы можем подставить в формулу [latex]h+a[/latex]. Теперь формула приобретает следующий вид: [latex]S=[/latex][latex]\frac{1}{2}\cdot h \cdot \left (h+a \right )[/latex]
Cовершив некоторые преобразования приходим к квадратному уравнению [latex]h^{2}+a\cdot h-2\cdot S = 0[/latex]
Далее находим дискриминант по формуле [latex]D = a^{2}+4\cdot2\cdot S[/latex]. Находим корень квадратный из дискриминанта [latex]\sqrt{D}[/latex]
Находим высоту по формуле [latex]h=\frac{-a+\sqrt{D}}{2}[/latex]
Второй корень нам не подходит, потому что он меньше [latex]0[/latex], а длина не может быть отрицательной.
Подставляем исходные данные в формулы, получаем результат.

Также подробное описание представлено в коде программы.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

Related Images:

Ю1.26

21/12/2014 by Сіренко Валерія Сергіївна

Задача:

Треугольник задается координатами своих вершин на плоскости : [latex]A(x_{1} , y_{2})[/latex] , [latex]B(x_{2} , y_{2})[/latex] , [latex]C(x_{3} , y_{3})[/latex] . Найти длину и основание высоты, опущенной из вершины A на сторону ВС.

Тесты

[latex]x_{А}[/latex]	[latex]y_{A}[/latex]	[latex]x_{B}[/latex]	[latex]y_{B}[/latex]	[latex]x_{C}[/latex]	[latex]y_{C}[/latex]	Основание ([latex]BC[/latex])	Высота[latex]h[/latex]	Комментарий
7	9	45	9	34	5	11	13	пройден
0.75	1	0.25	2	0.5	3	1	0	пройден
98	67	56	47	34	95	52	47	пройден
0	1	0	3	0	4	1	0	пройден

В четвертом примере имеем вырожденный треугольник, для которого площадь будет равна нулю , следовательно и высота так же равна 0

Код:

#include <iostream>
#include <math.h>
using namespace std;
 
int main(){
    double xA, yA, xB, yB, xC, yC; int h, S, AB, BC, AC;
    cin>>xA>>yA>>xB>>yB>>xC>>yC;
    AB = sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));
    BC = sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));
    AC = sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));
    {
	if((AB>BC+AC)&&(BC>AB+AC)&&(AC>AB+BC))
	{
		cout << ("Treygolnik ne syshestvyet");
	}
	else
	{
		S = fabs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))/2.0; 
 		h = (2*S)/ BC;
	 	cout << BC << " " << h;
	 }
    }
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main(){

double xA, yA, xB, yB, xC, yC; int h, S, AB, BC, AC;

cin>>xA>>yA>>xB>>yB>>xC>>yC;

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

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

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

{

if((AB>BC+AC)&&(BC>AB+AC)&&(AC>AB+BC))

{

cout << ("Treygolnik ne syshestvyet");

}

else

{

S = fabs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))/2.0;

h = (2*S)/ BC;

cout << BC << " " << h;

}

return 0;

}

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double xA, yA, xB, yB, xC, yC; double h, S, AB, BC, AC;
	        Scanner in = new Scanner(System.in);
	        xA = in.nextDouble();
	        yA = in.nextDouble();
	        xB = in.nextDouble();
	        yB = in.nextDouble();
	        xC = in.nextDouble();
	        yC = in.nextDouble();
	        AB = Math.sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));
	        BC = Math.sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));
	        AC = Math.sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));
		if((AB>BC+AC)&&(BC>AB+AC)&&(AC>AB+BC))
		{
			System.out.printf("Treygolnik ne syshestvyet");
		}
		else
		{
			S = Math.abs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))/2.0; 
	 		h = (2*S)/ BC;
		 	System.out.printf("BC");
		 	System.out.printf(" ");
		 	System.out.printf("%.1f",h);	
		 }
	}	 
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone

{

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

{

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

Scanner in = new Scanner(System.in);

xA = in.nextDouble();

yA = in.nextDouble();

xB = in.nextDouble();

yB = in.nextDouble();

xC = in.nextDouble();

yC = in.nextDouble();

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

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

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

if((AB>BC+AC)&&(BC>AB+AC)&&(AC>AB+BC))

{

System.out.printf("Treygolnik ne syshestvyet");

}

else

{

S = Math.abs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))/2.0;

h = (2*S)/ BC;

System.out.printf("BC");

System.out.printf(" ");

System.out.printf("%.1f",h);

}

ссылка на C++ : http://ideone.com/fBfd8S

ссылка на Java : http://ideone.com/ut9G6J

Решение:

Для начала находим стороны треугольника :

 AB = sqrt((xB-xA)*(xB-xA)+(yB-yA)*(yB-yA));
 BC = sqrt((xC-xB)*(xC-xB)+(yC-yB)*(yC-yB));
 AC = sqrt((xA-xC)*(xA-xC)+(yA-yC)*(yA-yC));

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

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

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

далее выполняем условие , что если сумма двух сторон меньше третей то треугольник не существует. Если же наоборот начинаем считать плащадь треугольника по формуле :

S = fabs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))/2.0;

18	S = fabs((xB-xA)(yC-yA)-(xC-xA)(yB-yA))/2.0;

и с помощью площади находим высоту :

h = (2*S)/ BC;

19	h = (2*S)/ BC;

и в конце выводим высоту и основание.

Related Images:

Ю1.16

18/09/2014 by Божик Семен

Задача: в равнобедренном прямоугольном треугольнике известна высота h, опущенная на гипотенузу. Найти стороны треугольника.

h	a	b	c	Комментарий
5	7.07107	7.07107	10	Пройдено.
7	9.89949	9.89949	14	Пройдено.
3.53553	5	5	7.07106	Пройдено.

#include <iostream>
#include <cmath>

double h, a, b, c;
 
int main() {
 scanf("%lg", &h);
 c=2*h;
 a=c/sqrt(2);
 b=a;
 printf("%lg%s%lg%s%lg%s%lg%s",h," h\n", a," a\n", b," b\n", c, " c");
 return 0;
}

#include <iostream>

#include <cmath>

double h, a, b, c;

int main() {

scanf("%lg", &h);

c=2*h;

a=c/sqrt(2);

b=a;

printf("%lg%s%lg%s%lg%s%lg%s",h," h\n", a," a\n", b," b\n", c, " c");

return 0;

}

Довольно простая задача в виду того, что прямоугольный равнобедренный треугольник это квадрат с сечением по диагонали. Диагональ [latex]c=a\sqrt { 2 } [/latex], а

[latex]h=\frac { a\sqrt {2}}{2}[/latex], т.к. это половина диагонали.

Из этого следует, что [latex]a=\frac{c}{\sqrt{ 2 }}[/latex], [latex]a=b[/latex]

Алгоритм выполнения задачи:

1. Узнаю [latex]c=2h[/latex]

2. Узнаю [latex]a=\frac{c}{\sqrt{ 2 }}[/latex], [latex]a=b[/latex]

Вывод: В виду того, что треугольник равнобедренный, задача не вызывает никаких трудностей и легко решаема.