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:

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:

Кольцo

09/11/2017 by Илья Черноморец

Заданы площадь кольца и радиус внешней окружности. Определить радиус внутренней окружности. Continue reading →

Related Images:

КМ 29. Монеты

08/11/2016 by Герман Веранян

Задача

Задача из журнала «Квант» №6 1970 г. стр. 28 В.И.Арнольд

[latex]n[/latex] одинаковых монет лежат на столе, образую замкнутую цепочку. Сколько оборотов сделает монета [latex]M[/latex] такого же размера за то время, пока она один раз обкатится по внешней стороне всей цепочки, как показано на рисунке (монета [latex]M[/latex] =2 коп.)?
Как изменится ответ, если монета [latex]M[/latex] будет иметь радиус, отличающийся в [latex]k[/latex] раз от радиуса каждой из монет в цепочке?

Представлю вам предложенное для данной задачи изображение из самого журнала.

Тесты

Входные данные			Выходные данные
№	[latex]n[/latex]	[latex]k[/latex]	Количество оборотов
1	3	1	3
2	12	1	6
3	182	1	62.667
4	12	2.22	3.19998
5	145	2.28101	22
6	8	0.53884	8

Код.

#include <iostream> 
#include <cmath> 
using namespace std;
 
int main(){
   double n, k;
   cin >> n >> k;
   if (k==1) cout << ((n/3)+2);
   else cout << ((k+1)/(2*k))*(n-(2/M_PI)*n*acos(1/(k+1))+2);
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double n, k;

cin >> n >> k;

if (k==1) cout << ((n/3)+2);

else cout << ((k+1)/(2*k))*(n-(2/M_PI)*n*acos(1/(k+1))+2);

return 0;

}

Решение.

Примем радиус монет, составляющих цепочку, за единицу. За то время, пока монета радиуса [latex]k[/latex] прокатится по дуге [latex]\alpha[/latex] неподвижной окружности радиуса 1, она повернется на угол [latex]\alpha(1+1/k)[/latex] следовательно весь угол на который повернётся монета, равен [latex]\alpha+\alpha/k[/latex](в частности, при [latex]k[/latex]=1 этот угол равен 2[latex]\alpha[/latex]).
Теперь найдем сумму дуг,состоящих из таких точек неподвижных монет, которых монета [latex]M[/latex] касалась при качении по цепочке. Если принять центры монет цепочки за точки [latex]O_1[/latex], [latex]O_2[/latex], … , [latex]O_n[/latex], то сумма дуг, лежащих внутри многоугольника [latex]O_1[/latex][latex]O_2[/latex]…[latex]O_n[/latex], равна сумме его внутренних углов, то есть [latex]\pi(n-2)[/latex]. Сумма дуг, лежащих вне многоугольника, следовательно, равна [latex]\pi(n+2)[/latex].Из неё нужно вычесть ещё сумму дуг лежащих в углублениях между двумя соседними монетами, в которые [latex]M[/latex] не попадает. В каждом из [latex]n[/latex] углублений сумма двух таких дуг равна [latex]2\pi/3[/latex] при [latex]k[/latex]=1 и [latex]2arccos\frac{1}{k+1}[/latex] в общем случае. Итак, сумма дуг, по которым прокатится монета [latex]M[/latex], равна [latex]\pi(n+2)-2\pi n/3[/latex] (в общем случае [latex]\pi(n+2)-2n\arccos\frac{1}{k+1}[/latex]. Чтобы узнать искомое число оборотов, нужно умножить эту велечину на [latex]2[/latex]( в общем случае на [latex]1+1/k[/latex]) и разделить на 2[latex]\pi[/latex].
А значит ответ ([latex]\frac{n}{3}+2[/latex]) оборота при k=1, и [latex]\frac{k+1}{2k}(n-\frac{2}{\pi}n \arccos\frac{1}{k+1}+2)[/latex] оборота в общем случае.

Ссылка на решение:Ideone

Related Images:

A60г

31/10/2016 by Алла Марокко

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть u определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом: [latex] u=\begin{cases}x^{2}-1, ; \text{ if } (x, y)\in D \\sqrt{\left| x-1 \right| } ; \text{ another case }\end{cases}[/latex] (запись [latex] (x, y)\in D [/latex] означает, что точка с координатами [latex]x, y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y.[/latex] Определить [latex]u.[/latex]

Тесты:

№	Вход		Выход
	[latex]x[/latex]	[latex]y[/latex]	[latex]u[/latex]
1	0.3	0.3	0.836660
2	1	1	0.000000
3	2	2	1.000000
4	0	0	-1.000000

Код на языке C++:

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

int main() {
    float x, y, u;
    scanf("%f%f", &x, &y);
    float a=x*x+y*y;
    if((y<0)||(a>1)||((x>0)&&(a<0.3)))
    {
        printf("u=%f", sqrt(abs(x-1)));
    }
    else
    {
        printf("u=%f",x*x-1);
    }

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

float x, y, u;

scanf("%f%f", &x, &y);

float a=x*x+y*y;

if((y<0)||(a>1)||((x>0)&&(a<0.3)))

{

printf("u=%f", sqrt(abs(x-1)));

}

else

{

printf("u=%f",x*x-1);

}

return 0;

}

Код на языке Java:

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


class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        float x = in.nextFloat();
        float y = in.nextFloat();
        float a=x*x+y*y;
        if((y<0)||(a>1)||((x>0)&&(a<0.3))){
            System.out.println(Math.sqrt(Math.abs(x-1)));
        }
        else{
            System.out.println(x*x-1);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

float x = in.nextFloat();

float y = in.nextFloat();

float a=x*x+y*y;

if((y<0)||(a>1)||((x>0)&&(a<0.3))){

System.out.println(Math.sqrt(Math.abs(x-1)));

}

else{

System.out.println(x*x-1);

}

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex] y<0 [/latex].Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3 .
Ссылки:
Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .

Related Images:

ML30. Объём параллелепипеда

29/10/2016 by Оля Вдовиченко

Задача. Найти объём параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z),[/latex] [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z).[/latex]

Входные данные: Координаты векторов [latex]\overrightarrow{a},[/latex] [latex] \overrightarrow{b},[/latex] [latex]\overrightarrow{c}. [/latex]

Выходные данные: Объём параллелепипеда.

Тесты

Входные данные	Выходные данные
0 0 1 0 1 0 1 0 0	1
0 0 0 1 0 0 0 0 1	0
1 0 0 0 0 1 0 0 1	0
2 5 3 4 1 0 -2 7 6	18
3 5 1 0 -7 2 6 -4 5	21

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

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

int main() {
    double ax, ay, az, bx, by, bz, cx, cy, cz, V, V1;
    cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz; //Ввод координат векторов.
    V = (ax*((by*cz)+(cy*bz)))-ay*((bx*cz)+(cx*bz))+az*((bx*cy)+(cx*by)); //Вычисление объёма.
    cout << abs(V); //Выводим модуль значения определителя.
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double ax, ay, az, bx, by, bz, cx, cy, cz, V, V1;

cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz; //Ввод координат векторов.

V = (ax*((by*cz)+(cy*bz)))-ay*((bx*cz)+(cx*bz))+az*((bx*cy)+(cx*by)); //Вычисление объёма.

cout << abs(V); //Выводим модуль значения определителя.

return 0;

}

Решение

Для решения данной задачи можно составить матрицу и вывести из неё формулу для нахождения определителя:
[latex]\triangle = \begin{vmatrix}a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z\end{vmatrix} =[/latex] [latex] a_x \left(b_y c_z+c_y b_z\right)[/latex] [latex]-a_y \left(b_x c_z+c_x b_z\right)+[/latex] [latex]a_z\left(b_x c_y+c_x b_y\right).[/latex]

Модуль определителя матрицы равен объёму параллелепипеда.

Решение на ideone.

Related Images:

KM63

06/10/2016 by Курьянов Павел

Задача М63 из журнала «Квант» №1 за 1971 год, стр.39. Автор А.А. Кириллов.
Можно ли из плиток размером 1х2 сложить четырехугольник размером [latex] M\times N [/latex] так, чтоб при этом не было ни одного прямого «шва», соединяющего стороны квадрата и идущие по краям плиток.

Изображение как на рисунке не годиться так как тут есть «шов» [latex] AB [/latex].

Входные данные
Размеры четырёхугольника [latex] M [/latex] и [latex] N [/latex].

Выходные данные
Возможно ли это сделать [latex] Yes [/latex] или не возможно [latex] No [/latex].

Тесты

вводимые данные		выводимые данные
M	N	возможно \|\| не возможно
2	16	no
6	6	no
66	69	yes
16	5	yes
99	71	no
7	7	no
78	77	yes
7	8	yes

Код задачи

#include <iostream>
using namespace std;

int main() {
    long long m,n;
    cin>>m>>n;
    if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {  
        if (m==6 && n==6) {
            cout<<"No";// согласно решению задачи
            return 0;
        }
        cout<<"Yes";//согласно общему решению
    }
    else{ 
        cout<<"No";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long m,n;

cin>>m>>n;

if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {

if (m==6 && n==6) {

cout<<"No";// согласно решению задачи

return 0;

}

cout<<"Yes";//согласно общему решению

}

else{

cout<<"No";

}

return 0;

}

Решение
Легко доказать, что прямоугольники [latex] {2\times m}, [/latex] [latex] {3\times m}, [/latex] [latex] {4\times m} [/latex] разрезать таким образом нельзя. Если же [latex] {m\geq{5}}, [/latex] [latex] {n\geq{5}} [/latex] и [latex] mn [/latex] четно (последнее условие разумеется необходимо), то во всех случаях кроме [latex]{6\times 6}[/latex] нужное разбиение существует.
Ссылки
ideone

Related Images:

ML 27. Угол между векторами

03/10/2016 by Лена Бригарь

Условие:

Найти угол в градусах, минутах и секундах между векторами [latex]\overrightarrow{a}=(a_x,a_y,a_z)[/latex] и [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex].

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

Координаты векторов [latex] \overrightarrow{a}[/latex] и [latex]\overrightarrow{b}[/latex].

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

Угол в градусах, минутах и секундах.

Тесты

№	Входные данные	Выходные данные
1	1 1 4 20 31 12	53° 1′ 23″
2	1 61 12 1 11 1	7° 17′ 33″
3	1 0 0 0 0 1	90° 0′ 0″
4	-1 0 1 -2 2 1	44° 59′ 59″

Код

#define _USE_MATH_DEFINES
#include 
#include 
using namespace std;

int main() {
    double ax, ay, az, bx, by, bz, mdla, mdlb, mdlab, ccos, ugl;
    int gr = 0,mn=0, sc=0;
    cin >> ax >> ay >> az >> bx >> by >> bz;
    mdla = sqrt(ax*ax + ay*ay + az*az); //формула длины вектора
    mdlb = sqrt(bx*bx + by*by + bz*bz);
    mdlab = mdla*mdlb;
    ccos = (ax*bx + ay*by + az*bz) / mdlab; // формула косинус угла между векторами
    ugl = acos(ccos)*180/M_PI;// получим угол по формуле перевода радиан в градусы
    gr = ugl; // найдем градусы
    ugl -= gr;
    mn = ugl * 60; // оставшаяся часть угла в минутах
    ugl -= (double)mn / 60;
    sc = ugl * 3600; // оставшаяся часть угла в секундах
    cout << gr << "° " << mn << "' " << sc << "''";
    return 0;
}

#define _USE_MATH_DEFINES

#include

using namespace std;

int main() {

double ax, ay, az, bx, by, bz, mdla, mdlb, mdlab, ccos, ugl;

int gr = 0,mn=0, sc=0;

cin >> ax >> ay >> az >> bx >> by >> bz;

mdla = sqrt(ax*ax + ay*ay + az*az); //формула длины вектора

mdlb = sqrt(bx*bx + by*by + bz*bz);

mdlab = mdla*mdlb;

ccos = (ax*bx + ay*by + az*bz) / mdlab; // формула косинус угла между векторами

ugl = acos(ccos)*180/M_PI;// получим угол по формуле перевода радиан в градусы

gr = ugl; // найдем градусы

ugl -= gr;

mn = ugl * 60; // оставшаяся часть угла в минутах

ugl -= (double)mn / 60;

sc = ugl * 3600; // оставшаяся часть угла в секундах

cout << gr << "° " << mn << "' " << sc << "''";

return 0;

}

Решение:

Для решения данной задачи необходимо найти косинус между векторами, а после перевести радианы в градусы.
Косинус между векторами найдем по формуле [latex] \cos \alpha = \frac{\vec{a}\vec{b}}{\left|\vec{a} \right|\left|\vec{b} \right|}[/latex] .
Скалярное произведение найдем по формуле [latex] \left|\vec{a} \right| \left|\vec{b} \right|={a}_{x}{b}_{x}+{a}_{y}{b}_{y}+{a}_{z}{b}_{z} [/latex] .
Модуль вектора найдем по формуле [latex] \left|\vec{a} \right| = \sqrt{ {{a}_{x}}^{2}+{{a}_{y}}^{2}+{{a}_{z}}^{2} } [/latex] ; [latex] \left|\vec{b} \right| = \sqrt{ {{b}_{x}}^{2}+{{b}_{y}}^{2}+{{b}_{z}}^{2} } [/latex] .
Затем переведем радианы в градусы по формуле [latex] \frac{180}{ \arccos (-1.0) \arccos (\cos \alpha )} [/latex] .
[latex] \arccos (-1.0) [/latex] это число [latex] \pi [/latex] .

Ссылки:

Решение задачи на ideone.com: http://ideone.com/Gx3IVU
Косинус угла между векторами: http://ru.onlinemschool.com/math/library/vector/angl/
Скалярное произведение векторов: http://ru.onlinemschool.com/math/library/vector/multiply/
Модуль вектора: http://ru.onlinemschool.com/math/library/vector/length/
Перевод радиан в градусы: http://www.cleverstudents.ru/trigonometry/radian_and_degree_conversion.html
Условие задачи: https://cpp.mazurok.com/mtasks/

Related Images:

KM31. Бумажные многоугольники

02/10/2016 by Тимур Фирсов

Задача

Задача из журнала «Квант» №7 1970 г.
Квадратный лист бумаги разрезают по прямой на две части. Одну из полученных частей снова разрезают на две части, и так делают много раз. Какое наименьшее число разрезов [latex]r[/latex] нужно сделать, чтобы среди полученных частей оказалось [latex]n[/latex] [latex]k[/latex] -угольников?

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

Количество многоугольников [latex]n[/latex].
Количество углов многоугольника [latex]k[/latex].

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

Количество разрезов [latex]r[/latex].

Пример получения двух шестиугольников за 5 разрезов

Тесты

	Входные данные		Выходные данные
№	[latex]n[/latex]	[latex]k[/latex]	[latex]r[/latex]
1	100	20	1699
2	14	3	13
3	1	3	1
4	40	360	14279
5	2	6	5

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

#include <iostream>
using namespace std;
 
int main() {
    int r, n, k;
    cin>>n>>k;
    r=k>3? n*(k-3)-1 : n>1? n-1 : 1;
    cout<<r;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, n, k;

cin>>n>>k;

r=k>3? n*(k-3)-1 : n>1? n-1 : 1;

cout<<r;

return 0;

}

Решение

При каждом разрезе количество кусков бумаги [latex]n[/latex] увеличивается на [latex]1[/latex]. Общее количество вершин [latex]k[/latex] будет увеличиваться в зависимости от места разреза. Таким образом при разрезе через две стороны общее количество вершин будет увеличиваться на [latex]4[/latex]. При разрезе через две вершины общее количество вершин увеличивается на [latex]2[/latex], а при разрезе через сторону и вершину — на [latex]3[/latex].

При [latex]k>3[/latex] сначала разделим лист на [latex]n[/latex] четырёхугольников при помощи разрезов через противоположные стороны. На это нам понадобиться [latex]n-1[/latex] разрезов. Затем можем, при помощи разрезов через соседние стороны, превращать каждый четырехугольник в [latex]k[/latex] — угольник, на что понадобиться [latex]k-4[/latex] разрезов.Выходит, что на получение [latex]n[/latex] [latex]k[/latex]- угольников нужно сделать не меньше [latex]n(k-4)+n-1[/latex] разрезов, значит [latex]r=n(k-3)-1[/latex].

Если же [latex]k=3[/latex], то нам нужно, наоборот, уменьшить количество вершин. Тогда первый разрез сделаем через две вершины квадрата — получаем два треугольника, затем каждым разрезом через вершину и сторону увеличиваем количество треугольников на [latex]1[/latex] пока не получим [latex]n[/latex]. В таком случае [latex]r= n-1 [/latex]. Исключение: если [latex]n=1[/latex], то [latex]r=1.[/latex]

Ссылки

Код программы.
Условие задачи (страница 47).

Related Images:

KM139. Параллелограмм

01/10/2016 by Валентина Андриеш

Задача из журнала «Квант» №4 1972 г.
Из вершины [latex]B[/latex] параллелограмма [latex]ABCD[/latex] проведены его высоты [latex]BK[/latex] и [latex]BH[/latex]. Выразите расстояние от точки [latex]B[/latex] до точки пересечения высот треугольника [latex]BKH[/latex] через длины отрезков [latex]KH = a[/latex] и [latex]BD = b[/latex].

Входные данные:
Длины отрезков [latex]a[/latex], [latex]b[/latex]

Выходные данные:
Расстояние от точки [latex]B[/latex] до точки [latex]O[/latex] — точки пересечения высот треугольника [latex]BKH[/latex] ([latex]c[/latex])

Тесты:

b	a	c
10	6	8
5	3	4
3	5	inf (Infinity)

Код программы на С++:

#include <iostream>
#include <cmath>
#include <limits>
using namespace std;
int main() {
    double b,a;
    double inf = std::numeric_limits<double>::infinity();
    double c;
    cin>>b>>a;
    c=(b<a)?inf:sqrt(b*b-a*a);
    cout<<c;
    return 0;
}

#include <iostream>

#include <cmath>

#include <limits>

using namespace std;

int main() {

double b,a;

double inf = std::numeric_limits<double>::infinity();

double c;

cin>>b>>a;

c=(b<a)?inf:sqrt(b*b-a*a);

cout<<c;

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 b=in.nextDouble();
        double a=in.nextDouble();
        double inf = 1.0 / 0;
        double c;
        c=(b<a)?inf:Math.sqrt(b*b-a*a);
        System.out.println(c);
    }
}

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 b=in.nextDouble();

double a=in.nextDouble();

double inf = 1.0 / 0;

double c;

c=(b<a)?inf:Math.sqrt(b*b-a*a);

System.out.println(c);

}

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

Рассмотрим параллелограмм [latex]ABCD[/latex]. Проведем высоты [latex]BH[/latex] и [latex]BK[/latex] соответственно к сторонам [latex]AD[/latex] и [latex]DC[/latex]. Соединив точки [latex]K[/latex] и [latex]H[/latex] линией, получаем треугольник [latex]BKH[/latex]. В нем проведем три высоты [latex]BD[/latex], [latex]HM[/latex], [latex]KE[/latex] к сторонам [latex]HK[/latex], [latex]BK[/latex], [latex]HB[/latex]. Точкой пересечения высот в треугольнике является точка [latex]O[/latex].
Проведем в параллелограмме высоту [latex]DL[/latex] к стороне [latex]BC[/latex]. Соединив точки [latex]L[/latex] и [latex]K[/latex] получаем треугольник [latex]LDK[/latex]. Если сдвинуть (параллельно) треугольник [latex]BHO[/latex] так, чтобы точка [latex]H[/latex] попала в точку [latex]D[/latex], то он полностью совпадет с треугольником [latex]LKD[/latex], поскольку отрезок [latex]HO[/latex] параллелен и равен [latex]DK[/latex], а отрезок [latex]BH[/latex] параллелен и равен [latex]LD[/latex]. Следовательно, [latex]BO=LK[/latex] и два треугольника равны.
Рассмотрим прямоугольный треугольник [latex]HKL[/latex], в котором сторона [latex]HK=a[/latex] и [latex]HL=b[/latex] по условию. По теореме Пифагора отыщем сторону KL: [latex]KL=\sqrt[]{b^{2}-a^{2}}[/latex].
Так как треугольник [latex]BOH[/latex] и треугольник [latex]LKD[/latex] равны, получаем что [latex]KL=BO[/latex]

Решение задачи на C++
Решение задачи на Java

Условие задачи можно найти здесь: http://www.kvant.info/zkm_tex/zkm_main.pdf

Related Images:

ML28. Объём тетраэдра

28/09/2016 by Вадим Гордийчук

Задача

Найти объём тетраэдра три стороны которого образованы векторами [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex].

Пояснительный рисунок

Пояснительный рисунок к ML28

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

Координаты векторов [latex]\vec {a}[/latex], [latex]\vec {b}[/latex], [latex]\vec {c}[/latex].

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

Объём тетраэдра.

Тесты

Входные данные									Выходные данные
[latex]x_a[/latex]	[latex]y_a[/latex]	[latex]z_a[/latex]	[latex]x_b[/latex]	[latex]y_b[/latex]	[latex]z_b[/latex]	[latex]x_c[/latex]	[latex]y_c[/latex]	[latex]z_c[/latex]	[latex]V[/latex]
0	0	1	0	1	0	1	0	0	0.166667
3	6	3	1	3	-2	2	2	2	3
0	0	0	1	3	-2	2	2	2	0

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

#include <iostream>
using namespace std;
int main()
{
    double Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz, V;
    cin >> Ax >> Ay >> Az >> Bx >> By >> Bz >> Cx >> Cy >> Cz; //Считывание координат векторов.
    V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0; //Подсчитывание объёма.
    if (V < 0) V *= -1; //Определитель матрицы может быть отрицательным числом, объём - нет. Поэтому если объём отрицательный, умножаем его на -1.
    cout << V; //Вывод объёма.
}

#include <iostream>

using namespace std;

int main()

{

double Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz, V;

cin >> Ax >> Ay >> Az >> Bx >> By >> Bz >> Cx >> Cy >> Cz; //Считывание координат векторов.

V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0; //Подсчитывание объёма.

if (V < 0) V *= -1; //Определитель матрицы может быть отрицательным числом, объём - нет. Поэтому если объём отрицательный, умножаем его на -1.

cout << V; //Вывод объёма.

}

import java.util.*;

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double
            Ax = in.nextDouble(),
            Ay = in.nextDouble(),
            Az = in.nextDouble(),
            Bx = in.nextDouble(),
            By = in.nextDouble(),
            Bz = in.nextDouble(),
            Cx = in.nextDouble(),
            Cy = in.nextDouble(),
            Cz = in.nextDouble();
        double V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0;
        if (V < 0) V *= -1;
        System.out.print(V);
    }
}

import java.util.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

double

Ax = in.nextDouble(),

Ay = in.nextDouble(),

Az = in.nextDouble(),

Bx = in.nextDouble(),

By = in.nextDouble(),

Bz = in.nextDouble(),

Cx = in.nextDouble(),

Cy = in.nextDouble(),

Cz = in.nextDouble();

double V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0;

if (V < 0) V *= -1;

System.out.print(V);

}

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

Так как тетраэдр построен на векторах [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex], для данной задачи оптимальным решением будет использовать следующие формулы:

[latex]V = \frac {|\Delta|} {6}[/latex], где [latex]V[/latex] — объём тетраэдра, а [latex]\Delta[/latex] — определитель матрицы.
[latex] \Delta =
\begin{vmatrix}
x_a & y_a & z_a \\
x_b & y_b & z_b \\
x_c & y_c & z_c
\end{vmatrix}
= x_a \left(y_b z_c-z_b y_c \right)-x_b \left( y_a z_c-z_a y_c \right)+x_c \left( y_a z_b-z_a y_b \right)
[/latex].

Итоги:

если значение определителя матрицы равно нулю, то либо некоторые из заданных векторов коллинеарны, либо нулевые, либо все они лежат в одной плоскости. Во всех этих случаях тетраэдр не может существовать, и программа выведет [latex]0[/latex];
если значение определителя не равно нулю, то программа вычислит объём тетраэдра. В случае, если определитель примет отрицательное значение, программа домножит значение объёма на [latex]-1[/latex], в результате чего оно станет положительным.

Ссылки

Related Images:

ML39. Старинное окно

28/09/2016 by Тимур Фирсов

Задача

Окно в университетской аудитории имеет форму прямоугольника с присоединенным в верхней части полукругом. Периметр всего окна равен [latex]P[/latex]. Определить радиус полукруга [latex]R[/latex], при котором площадь окна максимальна.
Входные данные: Периметр окна [latex]P[/latex].
Выходные данные: Радиус полукруга [latex]R.[/latex]

Тесты

	Входные данные	Выходные данные
№	[latex]P[/latex]	[latex]R[/latex]
1	100	14.0025
2	73	10.2218
3	14	1.96035
4	0	0

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

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    double P, R;
    cin>>P;
    R=P/(4+M_PI);
    cout<<R;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double P, R;

cin>>P;

R=P/(4+M_PI);

cout<<R;

return 0;

}

Решение

Университетское окно

Обозначим боковую сторону окна [latex]b[/latex], а нижнюю [latex]a[/latex]. [latex]R=\frac { a }{ 2 } [/latex], тогда периметр окна [latex]P=a+2b+\frac { \pi a }{ 2 } [/latex], а площадь равна сумме площадей прямоугольника и полукруга [latex]S=ab+\frac { \pi { a }^{ 2 } }{ 8 } [/latex]. Выразим сторону [latex]b[/latex] через [latex]a[/latex] и периметр [latex]P[/latex] : [latex]b=\frac { 2P-2a-\pi a }{ 4 } [/latex], тогда [latex]S=\frac { 4Pa-4a^{ 2 }-\pi a^{ 2 } }{ 8 } [/latex]. Вычислим производную функции [latex]S(a)[/latex]. [latex]S'(a)=\frac { 2P-4a-\pi a }{ 4 } [/latex], затем найдем точки экстремума функции:
[latex]\frac { 2P-4a-\pi a }{ 4 } =0[/latex], тогда [latex]a=\frac { 2P }{ 4+\pi } [/latex].
Найдём область допустимых значений для [latex]a[/latex]. Наибольшего значения [latex]a[/latex] достигает при [latex]b=0[/latex], [latex]P=a+ \frac {\pi a}{2}[/latex], соответственно [latex]a=\frac { 2P }{ 1+\pi } [/latex]. Значит областью допустимых значений является отрезок [latex][0; \frac { 2P }{ 2+\pi } ] [/latex]. Поскольку [latex]0 < \frac { 2P }{ 4+\pi } < \frac { 2P }{ 2+\pi }[/latex] делаем вывод, что [latex]a=\frac { 2P }{ 4+\pi } [/latex] попадет в область допустимых значений. Найдём максимальное значение функции на отрезке:
[latex]S(0)=0[/latex].
[latex]S(\frac { 2P }{ 4+\pi })= \frac { 4P ^ {2} }{ 32 + 8 \pi } [/latex].
[latex]S( \frac { 2P }{ 2+\pi })= \frac { 4P ^ {2} }{ 16 + 8 \pi } \cdot \frac { \pi }{ 2+ \pi } [/latex].
[latex] \frac {S(\frac { 2P }{ 4+\pi })}{S( \frac { 2P }{ 2+\pi })} = \frac { 4+4\pi +{ \pi }^{ 2 } }{ 4\pi +{ \pi }^{ 2 } } [/latex].
Тогда [latex]S(0) < S(\frac { 2P }{ 2+\pi }) < S(\frac { 2P }{ 4+\pi }) [/latex].
Значит площадь окна [latex]S[/latex] достигает максимального значения при [latex]a=\frac { 2P }{ 4+\pi }[/latex], из чего следует [latex]R=\frac { P }{ 4+\pi }[/latex].

Ссылка на код

ideone

Related Images:

ML38. Максимальный размер прямоугольника, вырезанного из круга

22/09/2016 by Эммануил Прокопов

Задача. Какого наибольшего размера прямоугольник можно вырезать из круга диаметра [latex]d[/latex], если известно, что длины его сторон образуют золотую пропорцию.

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

Единственное число — диаметр окружности.

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

Два числа — длины сторон прямоугольника.

Тесты.

№	Входные данные	Выходные данные
	[latex]d[/latex]	[latex]a[/latex]	[latex]b[/latex]
1	0	0	0
2	1	0.850651	0.525731
3	2	1.7013	1.05146
4	21	17.8638	11.0404
5	0.32	0.272208	0.168234
6	1.7	1.44611	0.893743
7	134	113.981	70.448

Код программы на C++.

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double a, b, f, d;
    cin >> d;
    f = (sqrt(5) + 1) / 2;
    b = d / sqrt (1 + f * f);
    a = b * f;
    cout << a << ' ' << b;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, b, f, d;

cin >> d;

f = (sqrt(5) + 1) / 2;

b = d / sqrt (1 + f * f);

a = b * f;

cout << a << ' ' << b;

return 0;

}

Код программы на Java.

import java.util.*;
import java.math.*;
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        double f = (Math.sqrt(5)+1)/2;
        double d = in.nextDouble();
        double b = d / Math.sqrt(1 + f * f);
        double a = b * f;
        System.out.print(a + " " + b);
    }
}

import java.util.*;

import java.math.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double f = (Math.sqrt(5)+1)/2;

double d = in.nextDouble();

double b = d / Math.sqrt(1 + f * f);

double a = b * f;

System.out.print(a + " " + b);

}

Решение.

Прямоугольник будет иметь наибольший размер в случае, когда его вершины лежат на окружности. Тогда, очевидно, диаметр окружности будет диагональю данного прямоугольника. Согласно условию, длины его сторон образуют золотую пропорцию. Это означает, что [latex]\frac { a }{ b } =\phi [/latex], где [latex]a[/latex] — длина большей стороны прямоугольника, [latex]b[/latex] — длина его меньшей стороны, а [latex]\phi=\frac { 1+\sqrt { 5 } }{ 2 } [/latex]. Отсюда [latex]a=b\cdot \phi[/latex]. По теореме Пифагора, [latex]{ a }^{ 2 }+{ b }^{ 2 }={ d }^{ 2 }[/latex]. Путём подстановки из предыдущего выражения и простых алгебраических преобразований получим формулу для вычисления длины меньшей стороны: [latex]b=d\cdot \sqrt { \frac { 1 }{ { \phi }^{ 2 }+1 } } [/latex].
Сначала для удобства находим значение [latex]\phi[/latex], затем — по указанным формулам длины сторон прямоугольника.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).

Related Images:

ML26. Площадь треугольника

22/09/2016 by Даниил Юдин

Задача.

Найти площадь треугольника по заданным координатам его вершин [latex] A(x_a,y_a,z_a )[/latex], [latex]B(x_b,y_b,z_b)[/latex] и [latex]C(x_c,y_c,z_c)[/latex].

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

Координаты вершин треугольника [latex]ABC[/latex]

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

Площадь [latex]S[/latex] треугольника [latex]ABC[/latex]

Тесты

Входные данные									Выходные данные
[latex]x_a [/latex]	[latex]y_a [/latex]	[latex]z_a [/latex]	[latex]x_b [/latex]	[latex]y_b [/latex]	[latex]z_b [/latex]	[latex]x_c [/latex]	[latex]y_c [/latex]	[latex]z_c [/latex]	[latex]S [/latex]
-2	1	2	3	-3	4	1	0	9	19.7864
-3	13	-5	6	11	12	4	8	18	50.5618
-6	0	4	5	1	3	-3	-1	-4	43.307
-6	-2.3	-8.2	1.9	-7.8	0.2	-8.5	3.4	-8.9	28.0909

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

#include <iostream>
#include <cmath>
using namespace std;
//функция высчитывает расстояние между двумя координатами, координаты передаются в функцию при вызове
double side(double ax,double bx,double ay,double by,double az,double bz){
    return sqrt((bx-ax)*(bx-ax)+(by-ay)*(by-ay)+(bz-az)*(bz-az));
}
int main() {
    double ax,ay,az,bx,by,bz,cx,cy,cz;
    cin>>ax>>ay>>az>>bx>>by>>bz>>cx>>cy>>cz;
    double a=side(bx,ax,by,ay,bz,az);
    double b=side(cx,ax,cy,ay,cz,az);
    double c=side(bx,cx,by,cy,bz,cz);
    double p=(a+b+c)/2;
    double s=sqrt(p*(p-a)*(p-b)*(p-c));
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

//функция высчитывает расстояние между двумя координатами, координаты передаются в функцию при вызове

double side(double ax,double bx,double ay,double by,double az,double bz){

return sqrt((bx-ax)*(bx-ax)+(by-ay)*(by-ay)+(bz-az)*(bz-az));

}

int main() {

double ax,ay,az,bx,by,bz,cx,cy,cz;

cin>>ax>>ay>>az>>bx>>by>>bz>>cx>>cy>>cz;

double a=side(bx,ax,by,ay,bz,az);

double b=side(cx,ax,cy,ay,cz,az);

double c=side(bx,cx,by,cy,bz,cz);

double p=(a+b+c)/2;

double s=sqrt(p*(p-a)*(p-b)*(p-c));

cout<<s;

return 0;

}

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

Используя известные нам координаты вершин треугольника и формулу вычисления расстояния между двумя точками в пространстве [latex]AB=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}[/latex] можно найти длины сторон треугольника [latex]ABC[/latex]. Для нахождения площади используем Формулу Герона[latex]AB=\sqrt{p*(p-a)*(p-b)*(p-c)}[/latex] перед этим находим полупериметр [latex]p[/latex] по формуле [latex]p=\frac{a+b+c}{2}[/latex] подставляем значение и выводим конечный результат.

Ссылки

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

Related Images:

Mif 11

15/09/2016 by Станислав Коциевский

Задача

Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин на плоскости.

Тесты

Входные данные	Результат работы программы
1 1 1 7 5 3 1 6	0
5 6 8 8 2 2 5 4	2
1 -1 1 -3 2 -2 4 -1	1
-5 -1 -5 -3 -2 -1 -3 -2	2
-1 1 -1 3 -4 2 -3 5	2.52982
1 4 3 6 3 4 5 4	1.41421

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

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

struct point //точка
{
    double x;
    double y;
};
struct straight //прямая в виде общего уравнения Ax + By + C = 0
{
    double A;
    double B;
    double C;
};
straight create_straight (point A, point B)
{
    straight s;
    s.A = A.y - B.y;
    s.B = B.x - A.x;
    s.C = A.x * B.y - B.x * A.y;
    return s;
}
double r (point A, point B) //расстояние между двумя точками
{
    return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));
}
point projection (point A, point B, point C) // проекция точки С на прямую AB
{
    double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB
    double y = A.x - B.x;
    double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));
    point H;
    H.x = C.x + x * L;
    H.y = C.y + y * L;
    return H;
}
point intersection (straight a, straight b) //точка пересечения прямых a и b
{
    point ans;
    ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);
    ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);
    return ans;
}
void check_projection (point A, point B, point C, double & min_dis)
{
    point H = projection(A,B,C);
    if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку
    {
        if (r(H,C) < min_dis)
        {
            min_dis = r(H,C);
        }
    }
}
double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются
{
    double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));
    check_projection (A,B,C,min_dis);
    check_projection (A,B,D,min_dis);
    check_projection (C,D,A,min_dis);
    check_projection (C,D,B,min_dis);
    return min_dis;
}
int main()
{
    point A,B,C,D;
    cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;
    straight AB = create_straight(A,B);
    straight CD = create_straight(C,D);
    if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых
    {
        cout<<distance_if_not_intersect(A,B,C,D);
    }
    else
    {
        point H = intersection(AB,CD);
        if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам
        (H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )
        {
            cout<<0;
        }
        else
        {
            cout<<distance_if_not_intersect(A,B,C,D);
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

struct point //точка

{

double x;

double y;

};

struct straight //прямая в виде общего уравнения Ax + By + C = 0

{

double A;

double B;

double C;

};

straight create_straight (point A, point B)

{

straight s;

s.A = A.y - B.y;

s.B = B.x - A.x;

s.C = A.x * B.y - B.x * A.y;

return s;

}

double r (point A, point B) //расстояние между двумя точками

{

return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));

}

point projection (point A, point B, point C) // проекция точки С на прямую AB

{

double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB

double y = A.x - B.x;

double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));

point H;

H.x = C.x + x * L;

H.y = C.y + y * L;

return H;

}

point intersection (straight a, straight b) //точка пересечения прямых a и b

{

point ans;

ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);

ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);

return ans;

}

void check_projection (point A, point B, point C, double & min_dis)

{

point H = projection(A,B,C);

if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку

{

if (r(H,C) < min_dis)

{

min_dis = r(H,C);

}

double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются

{

double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));

check_projection (A,B,C,min_dis);

check_projection (A,B,D,min_dis);

check_projection (C,D,A,min_dis);

check_projection (C,D,B,min_dis);

return min_dis;

}

int main()

{

point A,B,C,D;

cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;

straight AB = create_straight(A,B);

straight CD = create_straight(C,D);

if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых

{

cout<<distance_if_not_intersect(A,B,C,D);

}

else

{

point H = intersection(AB,CD);

if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам

(H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )

{

cout<<0;

}

else

{

cout<<distance_if_not_intersect(A,B,C,D);

}

return 0;

}

Решение

Основная идея состоит в том, что расстояние между непересекающимися отрезками [latex]AB[/latex] и [latex]CD[/latex] — это минимальная из длин, соединяющих вершины разных отрезков, и длин перпендикуляров, проведенных из вершины на противоположный отрезок. Подробнее о математической части поиска перпендикуляра тут. Кроме этого, отрезки могут пересекаться, что проверяется отдельно. В таком случае, расстояние между ними равно нулю.

Чтобы проверить, пересекаются ли отрезки, нужно сначала проверить, не параллельны ли они.Если они не параллельны, нужно найти точку пересечения прямых, на которых лежат отрезки, а затем проверить принадлежит ли она обоим отрезкам. Отрезки пересекаются тогда и только тогда, когда они лежат на пересекающихся прямых, точка пересечения которых принадлежит обоим отрезкам. Координаты точки пересечения находятся из системы уравнений прямых, на которых лежат отрезки.
[latex] \begin{cases} A_{1}x + B_{1}y + C_{1} = 0 \\ A_{2}x + B_{2}y + C_{2} = 0 \end{cases} [/latex]

Из первого уравнения: [latex]x = \frac{-B_{1}y-C_{1}}{A_{1}}[/latex]

Подставим [latex]x[/latex] во второе уравнение:

[latex] \frac{A_{2}}{A_{1}}(-B_{1}y-C_{1}) + B_{2}y + C_{2} = 0[/latex] [latex](*)[/latex]

Решив уравнение [latex](*)[/latex] получим:

[latex]y = \frac{C_{1}A_{2}-C_{2}A_{1}}{A_{1}B_{2}-A_{2}B_{1}}[/latex].

Тогда

[latex]x = \frac{C_{2}B_{1}-C_{1}B_{2}}{A_{1}B_{2}-A_{2}B_{1}}[/latex]

Ссылка на код на ideone

Related Images:

Mif 17.7

05/10/2015 by Станислав Коциевский

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex]y[/latex]) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Результат
-6	3	принадлежит
0	0	не принадлежит
2	-4	не принадлежит
— 1	2	принадлежит
-5	-2	принадлежит

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

#include <iostream>
using namespace std;
 
int main()
{
    double x, y;
    cin>>x>>y;
    cout<<(((x<=-1)&&(x>=-6)&&(y>=2)&&(y<=7))||((x<=-3)&&(x>=-6)&&(y>=-3)&&(y<=2))?"принадлежит":"не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

double x, y;

cin>>x>>y;

cout<<(((x<=-1)&&(x>=-6)&&(y>=2)&&(y<=7))||((x<=-3)&&(x>=-6)&&(y>=-3)&&(y<=2))?"принадлежит":"не принадлежит");

return 0;

}

Решение.

В данной задаче необходимо проверить подходят ли координаты точки под условия, описывающие фигуру. В этом варианте фигуру можно разбить на 2 прямоугольника. Тогда вышеуказанные условия выглядит так: [latex]-6<=x<=-1[/latex] и [latex]2<=y<=7[/latex] (это первый прямоугольник) или [latex]-6<=x<=-3[/latex] и [latex]-3<=y<=2[/latex] (соответственно, второй прямоугольник).

Здесь находится условие задачи

Ссылка на код на ideone.com

Related Images:

ML 20

27/09/2015 by Грешилов Константин

Задача

Найти площадь кольца, внутренний радиус которого равен [latex]r[/latex], а внешний – [latex]R[/latex] ([latex]r<R[/latex]).

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

В единственной строке указаны внешний и внутренний радиусы, разделенные пробелом.

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

Единственное число — площадь кольца.

Тесты:

R	r	Площадь кольца
3	2	15.708
12.921	7.903	328.28
25	3.5	1925.01
10.2531	1	327.122

Решение:

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

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double R, r;

cin>>R>>r;

cout<<R*R*M_PI-r*r*M_PI<<endl;

return 0;

}

Описание решения:

При решении данной задачи использовались две переменные типа [latex]double[/latex]. Так как в постановке задачи не было указано, какими могут быть числа, то для обхвата наибольшего диапазона чисел разумно использовать именно этот тип данных. Помимо этого, была использована константа из математической библиотеки [latex]cmath[/latex], а именно, константа числа [latex]\pi[/latex]: [latex]M[/latex]_[latex]PI[/latex].

Чтобы найти площадь кольца, образованного двумя окружностями, необходимо найти площадь круга, образованного внешним радиусом кольца, по формуле [latex]\pi\cdot R^2[/latex], и площадь круга, образованного внутренним радиусом кольца, по формуле [latex]\pi\cdot r^2[/latex]. Затем, из площади большего круга вычесть площадь меньшего.

Получаем формулу: [latex]\pi\cdot R^2 — \pi\cdot r^2[/latex]. Подставляя в формулу переменные и константы, получаем:

R*R*M_PI-r*r*M_PI

7	RRM_PI-rrM_PI

После выполнения всех операций перейдем на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

Related Images:

ML23

24/09/2015 by Молоканов Юрий

Условие

Найти длины биссектрис [latex]a_1[/latex], [latex]b_1[/latex], [latex]c_1[/latex] треугольника, если известны длины противоположных сторон [latex]a[/latex], [latex]b[/latex], [latex]c[/latex].

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

№	Входные данные	Выходные данные
1	6, 7, 9	7.35803, 6.49923, 4.67652
2	3.5, 4.5, 5.5	4.66027, 3.79967, 2.88195
3	100000, 100000, 100000	86602.5, 86602.5, 86602.5
4	1, 1.118034, 1.118034	1, 0.898056, 0.898056

Код

#include <iostream>
#include <cmath>
using namespace std;
 
double getL(double c, double a, double b) {    // Возвращает длину биссектрисы к стороне A при сторонах A, B, C
    double s = a + b;
    return sqrt(a * b * (s + c) * (s - c))/s;  // Формула длины биссектрисы через три стороны
}
 
int main() {
    double a, b, c;
    cin >> a >> b >> c;
    cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double getL(double c, double a, double b) { // Возвращает длину биссектрисы к стороне A при сторонах A, B, C

double s = a + b;

return sqrt(a * b * (s + c) * (s - c))/s; // Формула длины биссектрисы через три стороны

}

int main() {

double a, b, c;

cin >> a >> b >> c;

cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

return 0;

}

Решение

Для вычисления длины биссектрисы через три стороны произвольного треугольника воспользуемся формулой [latex]l_c = \frac{\sqrt{ab(a+b+c)(a+b-c)}}{a+b}[/latex], где:

[latex]l_c[/latex] — длина биссектрисы, проведенной к стороне [latex]c[/latex];
[latex]a[/latex], [latex]b[/latex], [latex]c[/latex] — стороны треугольника.

Формула достаточно громоздкая, а так как использовать мы ее будем трижды — для вычисления длины каждой из биссектрис, — имеет смысл написать функцию, которая бы получала длины трех сторон треугольника и возвращала длину биссектрисы, проведенной к первой из указанных сторон:

double getL(double c, double a, double b) {
	return sqrt(a * b * (a + b + c) * (a + b - c))/(a + b);
}

double getL(double c, double a, double b) {

return sqrt(a * b * (a + b + c) * (a + b - c))/(a + b);

}

Можно заметить, что сумма [latex]a+b[/latex] встречается в формуле три раза. Для лучшей читаемости и компактности кода заменим a + b на s :

double getL(double c, double a, double b) {
    double s = a + b;
    return sqrt(a * b * (s + c) * (s - c))/s;
}

double getL(double c, double a, double b) {

double s = a + b;

return sqrt(a * b * (s + c) * (s - c))/s;

}

Наконец, в главной функции после получения длин сторон треугольника остается вывести длины самих биссектрис. Для этого используем вышеописанную функцию getL , каждый раз меняя первый параметр (при этом порядок двух других не имеет значения):

cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

1	cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

Ссылки

Код программы на Ideone.com;

Формулы длины биссектрис в треугольнике;

Список задач на линейные вычисления.

Related Images:

e-olymp 929 Параллелограмм

14/09/2015 by Андрей Яроцкий

Задача взята с сайта e-olymp

Условие:

Задано 4 числа [latex]a, b, c, d[/latex] определяющие длины отрезков. Определить, можно ли с этих отрезков образовать параллелограмм.

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

В единственной строке задано 4 числа через пробел.

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

Вывести в единственной строке слово «YES«, если параллелограмм образовать можно или «NO» (без кавычек) в противном случае.

Тесты

№	Входные данные	Выходные данные
1	2 4 2 4	YES
2	2 4 2.5 4	NO

#include <iostream>
using namespace std;
int main() {
   double a,b,c,d;
   cin>>a>>b>>c>>d;
   cout<<((a==c && b==d)||(a==b && c==d])||(a==d && c==b)?"YES":"NO");
   return 0;
}

#include <iostream>

using namespace std;

int main() {

double a,b,c,d;

cin>>a>>b>>c>>d;

cout<<((a==c && b==d)||(a==b && c==d])||(a==d && c==b)?"YES":"NO");

return 0;

}

Решение:

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

[latex]a=c[/latex] и [latex]b=d[/latex];

[latex]a=b[/latex] и [latex]c=d[/latex];

[latex]a=d[/latex] и [latex]c=b[/latex],

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

Ссылку на полностью засчитанное решение на сайте e-olymp.com можно найти здесь

Related Images:

А26

23/10/2014 by Гусак Дмитро Євгенович

Задача:

Найти площадь сектора, радиус которого равен 13.7, а дуга содержит заданное число радиан [latex] \varphi[/latex].

Тесты:

Ввод	Вывод	Результат
1	93.845	Площадь найдена
-1	Неверный ввод	Неправильные данные, подсчет невозможен
0.7	65.691	Площадь найдена
8.36	784.544	Площадь найдена
0	Неверный ввод	Неправильные данные, подсчет невозможен
3.14	294.673	Площадь найдена

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

#include <iostream>
using namespace std;

int main() {
	double r = 13.7; //заданный радиус
	double radian;  //угол, вводимый вручную
	double square;  //площадь, выводимая на экран
	printf("Введите число радиан дуги:");
	scanf("%lf", &radian);
	if(radian <= 0)
	            {
		         printf("Неверный ввод \n");
	            }
	else
	            {
	               square = radian/2 * (r*r);
	               printf("%5.3lf \n",square);
	            }
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double r = 13.7; //заданный радиус

double radian; //угол, вводимый вручную

double square; //площадь, выводимая на экран

printf("Введите число радиан дуги:");

scanf("%lf", &radian);

if(radian <= 0)

{

printf("Неверный ввод \n");

}

else

{

square = radian/2 * (r*r);

printf("%5.3lf \n",square);

}

return 0;

}

Решение:
Площадь сектора находится по формуле [latex]S=\frac{\varphi}{2}r^2[/latex], после чего выводится на экран. В случае, если введённый угол меньше или равен нулю, программа выдает сообщение о неверном вводе.

Использованную формулу можно найти по этой ссылке, а здесь находится код в Ideone.