OCPC-2021. Задача G. Электрик возвращается (код решения)

22/12/2021 by Александр Мармалюк

Условие

Электрик Геннадий, постоялец палаты номер 404 заведения «Покосившийся Скворечник», прокрался ночью к ближайшей ЛЭП, чтобы наконец воплотить в жизнь свой план – отрезать кусок провода, находящийся между двумя соседними опорами, и отомстить лживой розетке из предыдущей задачи.

Он планирует реализовать это следующим образом: сначала просто забраться на вершину одной из опор, отрезать провод, закреплённый там, после чего спуститься на некоторую высоту вниз, возможно до земли. Далее Геннадий рассчитывает воспользоваться способностями человека-паука, которые, по его убеждению, открылись в нём после недавнего удара током: он выстрелит паутиной в некоторую произвольную точку соседнего столба, оттолкнется от первого столба и спустится по дуге окружности либо до второго столба, либо до земли. Разница высот в начале и конце такого спуска не должна превышать некоторую величину $l$, иначе наш новоявленный человек-паук рискует слишком сильно разогнаться и превратиться в человека-лепёшку. Затем электрик поднимется на вершину второго столба, чтобы отрезать закреплённый там провод, и спустится на землю.

Высоты столбов – $h_1$ и $h_2$, расстояние между ними – $d$. Геннадий не очень любит лазать вверх, поэтому он хочет разработать план таким образом, чтобы суммарная дистанция подъёмов была минимально возможной. Раз уж Вы взялись помогать ему, то доведите начатое до конца!

Единственная строка ввода содержит четыре целых числа $d$, $h_1, h_2, l$ $(1 \leqslant d, h_1, h_2, l \leqslant 10^6)$.

Выведите одно число – минимальную суммарную дистанцию подъёма Геннадия с точностью не хуже $10^-5$.

Тесты

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

5 5 5 5	10.00000
4 5 8 5	10.00000
4 8 5 1	13.00000
3 4 6 1	9.00000
15 2 7 8	9.00000
2 5 7 11	7.82843
1 35 38 2	38.16228

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

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
    double h1, h2, l, d, a, b, r;
    cin >> d >> a >> b >> l;
    h1 = min(a,b);
    h2 = max(a,b);
    double res = h1;
    h1 = min (h1, (h2 - ((d*d - l*l)/(2*l))));
    if (h1 < 0) r = h2;
    else r = (sqrt(d*d + (h2-h1)*(h2-h1)));
    res += min(r, h2);
    cout << fixed << setprecision(5) << res;
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h1, h2, l, d, a, b, r;

cin >> d >> a >> b >> l;

h1 = min(a,b);

h2 = max(a,b);

double res = h1;

h1 = min (h1, (h2 - ((d*d - l*l)/(2*l))));

if (h1 < 0) r = h2;

else r = (sqrt(d*d + (h2-h1)*(h2-h1)));

res += min(r, h2);

cout << fixed << setprecision(5) << res;

return 0;

}

Решение

Во-первых, поймем, что выгоднее сначала забраться на более низкий столб. Действительно, предположим, $h_1 \gt h_2$ и начинать электрик Геннадий будет с первого столба.

Заметим, что если Геннадий применит навыки человека-паука, то не сможет оказаться на втором столбе выше, чем $h_2-d$ (т.е. не выше точки $E_1$), поскольку перелетать он будет по дуге окружности, радиус которой не меньше $d$. С другой стороны, начиная с более низкого столба, он сможет перелететь в точку $E_3$ (предполагаем, что возможность воспользоваться способностью есть). При этом $H_1E_3=H_1H_2$.
Теперь сравним суммарное расстояние подъемов вверх по столбам. Если начинать с более высокого, то: $AH_1+H_2E_1=AE+H_1E+EH_2$.

С другой стороны, начиная с более низкого, получим:
$BH_2+E_3H_1=BH_2+H_1H_2$.
Заметим, что $BH_2=AE$, а по неравенству треугольника $H_1E+EH_2 \gt H_1H_2$. Отсюда и получаем, что начинать с более низкого столба экономнее.
В случае же, когда способность человека-паука применить нельзя или с её помощью Геннадий спускается до земли, не имеет значения, с какого столба начинать. Поэтому будем считать, что $h_1 \leqslant h_2$.

Забраться на более низкий столб обязательно входит в итоговую сумму. Кроме того, Геннадию либо надо будет подниматься на высоту, равную длине паутины (т.е. радиусу окружности), либо просто подняться на второй столб.

Для удобства обозначим $h_2-h_1$ через $\Delta h$, а отрезок $H_1H_2$ через $r$.
Чтобы была возможность использовать способность человека-паука, мы хотим добиться того, чтобы выполнялось следующее неравенство:
$$r — \Delta h \leqslant l $$.
Будем считать, что $h_1$ — это не высота первого столба, а высота, с которой Геннадий перелетать на второй столб (понятно, что ради удовлетворения ограничения $l$ Геннадий может только начать спускаться вниз).

Из треугольника $\Delta EH_1H_2$ выражаем $r$ :
$$r = \sqrt{d^2+\Delta h^2}.$$

Тогда неравенство принимает вид:
$$\sqrt{d^2+\Delta h^2)-\Delta h} \leqslant l,$$
$$d^2+\Delta h^2 \leqslant \frac{d^2 — l^2}{2l},$$
$$h_1 \leqslant h_2 — \frac{d^2 — l^2}{2l}.$$

Теперь понятно, что высота, с которой Геннадию надо стрелять паутиной, будет меньшим значением между выражением в правой части неравенства и высотой первого столба (в случае, если полученное нами выражение больше высоты столба, мы понимаем, что «стрелять» надо с только вершины столба).

Далее остается исключить случай, когда наше выражение отрицательное (что соответствует случаю, в котором Геннадию надо спуститься на землю и пешком перейти ко второму столбу или же на паутине перелететь только до земли, т.к. для того, чтобы совершить прыжок, удовлетворяющий ограничение $l$, герою необходимо спуститься на высоту ниже уровня земли, что невозможно).

Далее остается вычислить длину паутины по формуле $ r = \sqrt{d^2+\Delta h^2},$ принимая в качестве $h_1$ высоту, с которой надо стрелять паутиной, и прибавить полученную величину к высоте первого столба.

Решение задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 396. Дождь

24/11/2021 by Александр Мармалюк

Условие

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

Напишите программу, которая по координате $\ x_0\ $ точки появления капли над землей вычисляет координату $x$ точки соприкосновения капли с землей $\ \left(y = 0\right).\ $ Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $\ x_0\ $ точки появления капли $\ \left( 0 \lt x_0 \lt 10000\right)\ $ и количество отрезков-препятствий $\ N\ (0 \leqslant N \leqslant 100).\ $ Далее следует $\ N\ $ строк, каждая из которых содержит четыре разделенные пробелами числа $\ x_1,\ $ $\ y_1,\ $ $\ x_2,\ $ $\ y_2\ $ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $\ 0$\ до $\ 10000\ $, $\ x_1 \lt x_2,$ $y_1 \neq y_2.\ $ Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $\ x\ $ точки соприкосновения капли с землей.

Тесты

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

30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
7 5 1 6 10 8 5 3 8 2 6 10 11 9 9 10 14 12 6 6 12 7	8
4 4 1 1 3 3 2 3 0 6 7 3 5 2 6 5 9 6	4
8 3 8 6 2 4 7 4 9 3 6 1 10 2	2
2 3 5 9998 0 10000 7 9996 11 9994 4 9996 9 9993	9

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

#include <iostream>
#include <cmath>
#include <vector>
#define MAX_Y 10000;
using namespace std;
struct slide {
    double x1;
    double y1;
    double x2;
    double y2;
};
//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]
double f (slide x, double x0) {
    double dx = x.x2 - x.x1;
    double dy = x.y2 - x.y1;
    return ((dy*(x0 - x.x1))/dx + x.y1);
}
vector <slide> roof; //вектор всех крыш
//считывание и заполнение данных
void read (int n) {
    while (n--) {
        double a, b, c, d;
        slide x;
        cin >> a >> b >> c >> d;
        if (a < c) {
            x.x1 = a;
            x.y1 = b;
            x.x2 = c;
            x.y2 = d;
        }
        else
        {
            x.x1 = c;
            x.y1 = d;
            x.x2 = a;
            x.y2 = b;
        }
        roof.push_back(x);
    }
}
int main() {
    int n, x, y = MAX_Y + 1;
    slide a;
    cin >> x >> n;
    if (n == 0) {
        cout << x;
        return 0;
    }
    read (n);
    while (roof.size()) {
        int index = -1;
        int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей
        bool no_projection = true;
        for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х
            if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?
                no_projection = false;
                if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?
                    value = f(roof[i], x);
                    index = i;
                }
            }
            if (min(roof[i].y1, roof[i].y2) > y) {  //крыша целиком осталась выше?
                roof.erase(roof.begin() + i);
                i--;
            }
        }
        if ((roof.size() == 0) or (no_projection)) {  //если удалили все крыши или свободно падает на землю
            cout << x;
            return 0;
        }
        if (roof[index].y1 < roof[index].y2)  //какой конец крыши ниже?
            x = roof[index].x1;
        else
            x = roof[index].x2;
        y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату
        roof.erase(roof.begin() + index);
    }
    cout << x;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

#define MAX_Y 10000;

using namespace std;

struct slide {

double x1;

double y1;

double x2;

double y2;

};

//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]

double f (slide x, double x0) {

double dx = x.x2 - x.x1;

double dy = x.y2 - x.y1;

return ((dy*(x0 - x.x1))/dx + x.y1);

}

vector <slide> roof; //вектор всех крыш

//считывание и заполнение данных

void read (int n) {

while (n--) {

double a, b, c, d;

slide x;

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

if (a < c) {

x.x1 = a;

x.y1 = b;

x.x2 = c;

x.y2 = d;

}

else

{

x.x1 = c;

x.y1 = d;

x.x2 = a;

x.y2 = b;

}

roof.push_back(x);

}

int main() {

int n, x, y = MAX_Y + 1;

slide a;

cin >> x >> n;

if (n == 0) {

cout << x;

return 0;

}

read (n);

while (roof.size()) {

int index = -1;

int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей

bool no_projection = true;

for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х

if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?

no_projection = false;

if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?

value = f(roof[i], x);

index = i;

}

if (min(roof[i].y1, roof[i].y2) > y) { //крыша целиком осталась выше?

roof.erase(roof.begin() + i);

i--;

}

if ((roof.size() == 0) or (no_projection)) { //если удалили все крыши или свободно падает на землю

cout << x;

return 0;

}

if (roof[index].y1 < roof[index].y2) //какой конец крыши ниже?

x = roof[index].x1;

else

x = roof[index].x2;

y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату

roof.erase(roof.begin() + index);

}

cout << x;

return 0;

}

Решение

Для удобства создадим структуру slide, которая будет описывать координаты концов отрезка-крыши. Также будем считать, что первый конец отрезка находится левее (для этого будем менять местами точки в случае необходимости).
Будем представлять каждую крышу как отрезок прямой на плоскости. Для этого применим уравнение прямой по двум точкам, принадлежащим этой прямой:
$$\frac{x — x_1}{x_2 — x1}=\frac{y — y_1}{y_2 — y_1}$$
Чтобы проверить, может ли капля в текущий момент проектироваться на некоторую крышу, надо проверить, находится ли абсцисса капли между абсциссами концов отрезка-крыши, а также найти ту крышу, которая в абсциссе капли «выше всех» (другими словами, у какой из прямых, которым принадлежат те отрезки, на которые проектируется капля, наибольшее значение ординаты в абсциссе капли). Для этого создадим функцию, которая и будет возвращать искомое значение ординаты. Также важно убедиться в том, что эта крыша находится ниже текущего положения капли. Заметим, что если некоторая крыша целиком находится выше капли, то мы на неё уже никогда не попадем, поэтому её нужно удалить из вектора. Найдя нужную крышу, определим новые координаты капли после того, как она скатится по этой крыше. Если капля в свободном падении и на её пути больше нет препятствий (крыш не осталось или нет такой, на которую проектируется капля), то текущая абсцисса капли и будет ответом на задачу.

Ссылки

Условие задачи на eolymp.com
Решение задачи на ideone.com

Related Images:

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 365. Рамка

21/12/2019 by Александр Рапчинский

Задача

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

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

Заданы через пробел $8$ чисел — координаты начала и конца отрезка и координаты противоположных углов рамки. Координаты — целые числа, не превышающие по модулю $35000$.

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

Вывести одно число — длину части отрезка, которая оказалась внутри рамки.

Тесты

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

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

#include <iostream>
#include <algorithm>
using namespace std;
 
int distance(int a, int b, int c, int d) {
    int ans = 0;
    if (a > b) {
        swap(a, b);
    }
    if (c > d) {
        swap(c, d);
    }
    if (b < c || a > d) {
        ans = 0;
    } 
    else {
        int l = 0, r = 0;
        l = max(a, c);
        r = min(b, d);
        ans = r - l;
    }
    return ans;
}
 
int main() {
    int x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    if (x1 != x2) {
        cout << (y1 < max(y3, y4) && y1 > min(y3, y4) ? distance(x1, x2, x3, x4) : 0); 
    }
    else {
        cout << (x1 < max(x3, x4) && x1 > min(x3, x4) ? distance(y1, y2, y3, y4) : 0);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int distance(int a, int b, int c, int d) {

int ans = 0;

if (a > b) {

swap(a, b);

}

if (c > d) {

swap(c, d);

}

if (b < c || a > d) {

ans = 0;

}

else {

int l = 0, r = 0;

l = max(a, c);

r = min(b, d);

ans = r - l;

}

return ans;

}

int main() {

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

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

if (x1 != x2) {

cout << (y1 < max(y3, y4) && y1 > min(y3, y4) ? distance(x1, x2, x3, x4) : 0);

}

else {

cout << (x1 < max(x3, x4) && x1 > min(x3, x4) ? distance(y1, y2, y3, y4) : 0);

}

return 0;

}

Решение

Так как отрезок параллелен одной из сторон листка, то абсциссы (или ординаты) концов отрезка должны совпадать. Будем рассматривать случай когда они находятся между абсциссами (или ординатами соответственно) соответствующих вершин прямоугольника (в противном случае отрезок не проходит через рамку и ответ 0).

Если абсцисса левого или правого конца отрезка будет находиться, соответственно, правее крайней справа или левее крайней слева абсциссы вершины прямоугольника, то отрезок не проходит через рамку (для ординат аналогично).

В противном случае, отрезок проходит через рамку и мы можем подсчитать какая его часть находится внутри рамки. Для этого необходимо найти разность между абсциссами (ординатами) концов части отрезка находящийся внутри прямоугольника. Абсциссой левого конца такого отрезка будет максимальная из абсцисс левого конца изначального отрезка и крайней слева абсциссы прямоугольника, абсциссой правого конца такого отрезка будет минимальная из абсцисс правого конца изначального отрезка и крайней справа абсциссы прямоугольника (для ординат аналогично).

Обозначим искомую длину как $ans$, тогда $ans = min(x_{2}, x_{4})-max(x_{1}, x_{3})$.

Для ординат $ans = min(y_{2}, y_{4})-max(y_{1}, y_{3})$.

Ссылки

Условие задачи на e-olymp

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

Related Images:

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

Related Images:

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 774. Торт

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

Задача

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

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

Содержит три натуральных числа: радиус стола [latex]r \left(1\leqslant r\leqslant 1000 \right)[/latex], ширину [latex]w[/latex] и длину [latex]l[/latex] торта [latex] \left(1\leqslant w \leqslant l \leqslant 1000\right)[/latex].

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

Вывести слово [latex]YES[/latex], если торт помещается на стол, и слово [latex]NO[/latex] в противном случае.

Тесты

№	Входные данные	Выходные данные
1	38 40 60	YES
2	35 20 70	NO
3	50 60 80	YES
4	30 60 90	NO

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

с ветвлением:

#include <iostream>

using namespace std;
int main() {
    int r, w, l;
    cin >> r >> w >> l;
    cout << (w * w + l * l <= 4 * r * r ? "YES" : "NO");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, w, l;

cin >> r >> w >> l;

cout << (w * w + l * l <= 4 * r * r ? "YES" : "NO");

return 0;

}

без ветвления:

#include <iostream>
using namespace std;

bool myBool(int x, int y, int z) {
    return(x * x + y * y <= 4 * z * z);
}

int main() {
    int r, w, l;
    cin >> r >> w >> l;
    myBool(w, l, r) && cout << "YES";
    !myBool(w, l, r) && cout << "NO";
    return 0;
}

#include <iostream>

using namespace std;

bool myBool(int x, int y, int z) {

return(x * x + y * y <= 4 * z * z);

}

int main() {

int r, w, l;

cin >> r >> w >> l;

myBool(w, l, r) && cout << "YES";

!myBool(w, l, r) && cout << "NO";

return 0;

}

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

Вписанный в окружность прямоугольник

Для того, чтобы узнать, помещается торт на столе или нет, необходимо найти диагональ прямоугольного торта. Зная длину и ширину прямоугольника, находим диагональ по теореме Пифагора. Если она равна или меньше диаметра стола $AB^2$ + $AD^2$ <= 4$OD^2$, значит торт помещается, и пишем "YES". Если диагональ больше диаметра стола, пишем "NO".

Ссылки

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

Related Images:

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

22/12/2018 by Лиза Севастьянова

Задача

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

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

Целочисленные стороны прямоугольника $a$ и $b$ ($1 \leq a$, $b \leq 1000$).

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

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

Тесты

№	Входные данные	Выходные данные
1	3 4	12
2	5 12	60
3	1 1	1
4	1000 1000	1000000

Решение

Для нахождение площади прямоугольника воспользуемся формулой $S = a \cdot b$, где $a$ и $b$ — стороны данного прямоугольника, а $S$ — площадь прямоугольника.

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

#include <iostream>
using namespace std;

int main() {
    int  a;
    int b;
    cin >> a;
    cin >> b;
    cout << a*b;
}

#include <iostream>

using namespace std;

int main() {

int a;

int b;

cin >> a;

cin >> b;

cout << a*b;

}

Ссылки

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 8357. Точка в многоугольнике

05/12/2018 by Владислав Шеванов

Задача

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

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

В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

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

Тесты

Входные данные	Выходные данные
3 0 0 1 0 0 1 1 1	NO
4 3 2 0 0 1 5 5 5 6 0	YES
3 5 6 2 3 8 0 -1 -3	NO
4 -2 3 0 0 5 0 0 6 3 3	NO
5 3 1 9 2 3 0 -2 -4 -4 0 -4 5	YES

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

#include <iostream>
using namespace std;

struct point {
    int x;
    int y;
};

int f (point *p, int N, int x, int y) {
    int i1, i2, n, S, S1, S2, S3, flag;
    for (n = 0; n < N; n++) {
        flag = 0;
        i1 = n < N-1 ? n + 1 : 0;
        while (flag == 0) {
            i2 = i1 + 1;
            if (i2 >= N)
                i2 = 0;
            if (i2 == (n < N-1 ? n + 1 : 0))
                break;
            S = abs (p[i1].x * (p[i2].y - p[n].y) +
                p[i2].x * (p[n].y - p[i1].y) +
                p[n].x  * (p[i1].y - p[i2].y));
            S1 = abs (p[i1].x * (p[i2].y - y) +
                p[i2].x * (y - p[i1].y) +
                x * (p[i1].y - p[i2].y));
            S2 = abs (p[n ].x * (p[i2].y - y) +
                p[i2].x * (y - p[n].y) +
                x * (p[n].y - p[i2].y));
            S3 = abs (p[i1].x * (p[n].y - y) +
                p[n].x * (y - p[i1].y) +
                x * (p[i1].y - p[n].y));
            if (S == S1 + S2 + S3) {
                flag = 1;
                break;
            }
            i1++;
            if (i1 >= N)
                i1 = 0;
            }
        if (flag == 0)
            break;
    }
    return flag;
}

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    point* p = new point[n];
    for (int i = 0; i < n; i++)
        cin >> p[i].x >> p[i].y;
    cout << (f(p, n, x, y) ? "YES" : "NO");
    return 0;
}

#include <iostream>

using namespace std;

struct point {

int x;

int y;

};

int f (point *p, int N, int x, int y) {

int i1, i2, n, S, S1, S2, S3, flag;

for (n = 0; n < N; n++) {

flag = 0;

i1 = n < N-1 ? n + 1 : 0;

while (flag == 0) {

i2 = i1 + 1;

if (i2 >= N)

i2 = 0;

if (i2 == (n < N-1 ? n + 1 : 0))

break;

S = abs (p[i1].x * (p[i2].y - p[n].y) +

p[i2].x * (p[n].y - p[i1].y) +

p[n].x * (p[i1].y - p[i2].y));

S1 = abs (p[i1].x * (p[i2].y - y) +

p[i2].x * (y - p[i1].y) +

x * (p[i1].y - p[i2].y));

S2 = abs (p[n ].x * (p[i2].y - y) +

p[i2].x * (y - p[n].y) +

x * (p[n].y - p[i2].y));

S3 = abs (p[i1].x * (p[n].y - y) +

p[n].x * (y - p[i1].y) +

x * (p[i1].y - p[n].y));

if (S == S1 + S2 + S3) {

flag = 1;

break;

}

i1++;

if (i1 >= N)

i1 = 0;

}

if (flag == 0)

break;

}

return flag;

}

int main() {

int n, x, y;

cin >> n >> x >> y;

point* p = new point[n];

for (int i = 0; i < n; i++)

cin >> p[i].x >> p[i].y;

cout << (f(p, n, x, y) ? "YES" : "NO");

return 0;

}

Решение

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

Ссылки

Related Images:

e-olymp 2501. Круговая диаграмма

04/11/2018 by Александр Дьяченко

Задача

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

Исходными данными для этой диаграммы является набор чисел $a_1,\ldots, a_n, а$ диаграмма представляет собой круг радиуса $r$, разделенный на секторы. При этом каждому из чисел соответствует ровно один сектор, площадь которого пропорциональна этому числу. Общая площадь секторов равна площади круга.

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

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

Первая строка содержит два целых числа $n$ и $r \space (1 \leq n, r \leq 100)$. Вторая строка содержит $n$ целых чисел $a_1,\ldots, a_n \space (1 \leq a_i \leq 100$ для всех $i$ от $1$ до $n)$.

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

Выведите $n$ вещественных чисел — площади секторов, соответствующих числам $a_1,\ldots, a_n$. Выводите каждое из чисел в отдельной строке.

Все эти числа должны быть выведены с точностью не хуже $10^{-6}$.

Тесты

Входные данные	Выходные данные
3 2 1 4 3	1.570796327 6.283185307 4.712388980
2 3 3 8	7.711181968 20.563151914
4 5 2 5 9 1	9.239978393 23.099945982 41.579902768 4.619989196
5 9 4 16 8 20 11	17.252135928 69.008543713 34.504271856 86.260679641 47.443373803

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

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

int main() {
    int n, r, sum = 0;
    double S;
    cin >> n >> r;
    int *x = new int[n];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    for (int i = 0; i < n; i++)
        sum += x[i];
    S = M_PI * r * r;
    for (int i = 0; i < n; i++)
        cout << fixed << setprecision(9) << (S / sum) * x[i] << endl;
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

int n, r, sum = 0;

double S;

cin >> n >> r;

int *x = new int[n];

for (int i = 0; i < n; i++)

cin >> x[i];

for (int i = 0; i < n; i++)

sum += x[i];

S = M_PI * r * r;

for (int i = 0; i < n; i++)

cout << fixed << setprecision(9) << (S / sum) * x[i] << endl;

return 0;

}

Решение

Найдем сперва сумму всех чисел $a_i$ и площадь диаграммы (по известной формуле площади круга). Теперь можем легко посчитать площади каждого из секторов нашей диаграммы, разделив площадь последней на ранее найденную сумму и умножив их частное на соответствующее число $a_i$.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Related Images:

e-olymp 8372. Составить треугольник

28/09/2018 by Алина Гук

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

Задача

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

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

Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 6 7	YES
2	3 7 4	NO
3	16 24 32	YES
4	54 1 100	NO
5	1 1 1	YES

Код программы (Ветвление)

#include <iostream>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");

return 0;

}

Код программы (Линейные вычисления)

#include <iostream>
using namespace std;
 
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  bool condition = (a < b + c && b < a + c && c < a + b); 
  cout  << (char)(condition * 'Y' + !condition * 'N')
        << (char)(condition * 'E' + !condition * 'O')
        << (char)(condition * 'S' + !condition * ' ');
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

bool condition = (a < b + c && b < a + c && c < a + b);

cout << (char)(condition * 'Y' + !condition * 'N')

<< (char)(condition * 'E' + !condition * 'O')

<< (char)(condition * 'S' + !condition * ' ');

return 0;

}

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

Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}

Ссылки

Условие задачи на e-olymp

Код программы на ideone (Линейные вычисления)

Код программы на ideone (Ветвление)

Related Images:

e-olymp 1507. История Лаурела-Харди

26/09/2018 by Александр Дьяченко

Задача

Лаурел и Харди — два известных киногероя $50$-ых. Они известны своей разницей в весе, как можно увидеть на картинке. Если Вы еще не разобрались, кто из них кто, то я добавлю, что Лаурел легче. В свои юношеские годы Лаурел и Харди любили играть со странными качелями, и когда качели находились в равновесии, то Харди всегда был у земли. Мы рассмотрим двумерную версию качель.

Качели, которыми пользовались Лаурел и Харди, представляют собой часть окружности радиуса $r$, как показано на картинке (они закрашены серым и имеют вид буквы $D$). Харди сел на точку $B$ (самая правая точка качель), а Лаурел сел на точку $A$ (самая левая точка отрезка $AB$). $d = EF$ — расстояние между центром отрезка $AB$ и дуги $AFB$. То есть $E$ — середина отрезка $AB$, а $F$ — середина дуги $AFB$. $MN$ — основа качель, является горизонтальной прямой. $BD = h_1$ — расстояние от Харди до земли. Вам необходимо найти расстояние от Лаурела до земли (обозначаемое $h_2 = AC$).

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

Первая строка содержит количество тестов $N \space (0 < N ≤ 1000)$. Каждая из следующих $N$ строк представляет собой отдельный тест, который имеет следующий формат:

Каждая строка содержит три целых числа $r \space (10 ≤ r ≤ 100), \space$ $d \space (5 ≤ d ≤ r), \space$ $h_1 \space (5 ≤ h_1 ≤ d)$. Значение этих чисел приведено выше.

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

Для каждого теста в отдельной строке вывести его номер и действительной число — значение $h_2$. Это число должно содержать четыре десятичных знака. Формат вывода приведен в примере.

Тесты

Входные данные	Выходные данные
2 10 10 10 10 7 6	Case 1: 10.0000 Case 2: 8.0342
3 12 7 7 11 11 8 54 12 6	Case 1: 7.0000 Case 2: 14.0000 Case 3: 19.7383
5 94 21 12 23 9 8 5 4 3 2 2 1 43 26 20	Case 1: 32.1226 Case 2: 10.0439 Case 3: 5.0440 Case 4: 3.0000 Case 5: 32.4231

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

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

int main() {
    unsigned short N;
    double r, d, h_1, a, b;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> r >> d >> h_1;
        cout << "Case " << i << ": ";
        a = asin((r - h_1) / r) - asin((r - d) / r);
        if (a == 0)
            cout << fixed << setprecision(4) << h_1 << endl;
        else{
            b = 2 * sqrt(r * r - (r - d) * (r - d)) + h_1 / sin(a);
            cout << fixed << setprecision(4) << b * sin(a) << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

unsigned short N;

double r, d, h_1, a, b;

cin >> N;

for (int i = 1; i <= N; i++) {

cin >> r >> d >> h_1;

cout << "Case " << i << ": ";

a = asin((r - h_1) / r) - asin((r - d) / r);

if (a == 0)

cout << fixed << setprecision(4) << h_1 << endl;

else{

b = 2 * sqrt(r * r - (r - d) * (r - d)) + h_1 / sin(a);

cout << fixed << setprecision(4) << b * sin(a) << endl;

}

return 0;

}

Решение

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

В $9$ строке введем число $N$ из входного потока, а в $10$ — запустим цикл, который будет работать $N$ раз. Далее за каждый проход цикла будем читать по $3$ следующих числа из входного потока и выводить на экран номер текущего теста. Перед тем, как идти дальше, разберемся в рисунке. Так как по условию отрезок $EF$ делит сегмент $AFB$ пополам, то по свойствам хорд и дуг окружности, он является частью радиуса $r$ нашей окружности с центром в точке $O$ и перпендикулярен хорде $AB$, что и показано на чертеже. Кроме того, я дорисовал радиусы $OA$ и $OB$ окружности к соответствующим точкам и начертил отрезок $BH$, как продолжение $AB$, от точки $B$ до прямой $MN$. Также, я построил прямоугольный треугольник $\triangle OGB$, в котором катет $OG = r-BD$.
Достроив все необходимые отрезки, легко заметить, что мы имеем прямоугольный треугольник $\triangle ACH$ с катетом $AC$, длину которого нам и нужно найти по условию задачи. Предлагаю сделать это, воспользовавшись формулой $AC = AH \cdot \sin(\angle AHC)$. Найдем значения сомножителей.

Из рисунка очевидно, что $\angle AHC = \angle BHD = \angle EBG = \angle OBG-\angle OBE.$
Сначала найдем $\angle OBG$. Для этого рассмотрим треугольник $\triangle OGB$. Длины его гипотенузы и противолежащего к искомому углу катета нам уже известны, так что можем сразу найти $\angle OBG = \arcsin \frac{OG}{OB}$.
Теперь найдем $\angle OBE$. Рассмотрим прямоугольный треугольник $\triangle OEB$. В нем противолежащий искомому углу катет $OE = r-d$, а гипотенуза $OB = r$. Значит, $\angle OBE = \arcsin \frac{OE}{OB}$.
В итоге остаётся только найти разницу этих углов, которая и будет являться величиной искомого $\angle AHC$. В коде же значение этого угла считается в $13$ строке и присваивается переменной a.

Стоит заметить, что если $\angle OBG-\angle OBE = 0$, то длины отрезков $AC$ и $BD$, очевидно, совпадают. В таком случае можем сразу вывести на экран $h_2 = h_1$, как мы и поступили в $15$ строке, и перейти к нахождению $AC$ уже для следующего тестового случая.

Если же величина $\angle AHC$ отлична от $0$, то нам все еще предстоит посчитать длину гипотенузы $AH$ треугольника $\triangle ACH$. Она состоит из хорды $AB$ и отрезка $BH$.
Сперва найдем длину хорды. Известно, что $OF$ делит ее на $2$ одинаковых по длине отрезка, значит, следует опять рассмотреть треугольник $\triangle OEB$. Длину его гипотенузы и одного из катетов мы уже находили, так что просто применим теорему Пифагора и найдем $EB = \sqrt{OB^2-OE^2}$. Тогда $AB = 2 \cdot EB$.
Для нахождения длины $BH$, рассмотрим треугольник $\triangle BDH$, в котором этот отрезок является гипотенузой. Длину катета $BD$ и величину угла $\angle BHD$ мы уже знаем, значит, можем применить формулу $BH = \frac{BD}{\sin(\angle BHD)}$.
Сложим найденные значения длин хорды $AB$ и отрезка $BH$, чтобы получить $AH$. В коде эта длина находится в $17$ строке и присваивается переменной b.

Теперь остается только подставить найденные значения в ранее приведенную формулу и получить наконец длину $h_2$, которую выведем на экран в $18$ строке.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Related Images:

e-olymp 52. Сыр для Анфисы

13/05/2018 by Даниил Крутоголов

Сыр для Анфисы

Готовя обед для Анфисы — символа 2008 года, хозяин использовал для разрезания сыра специальный нож, который разрезал сыр на одинаковые прямоугольные паралелепипеды с основанием в виде квадрата со стороной [latex]a[/latex] и высотой [latex]b[/latex].
Но Анфиса, как и подобает даме года, любила употреблять сыр несколько меньших размеров, для чего она всегда разрезала предложенный кусочек деликатеса на две части, предварительно установив его строго вертикально квадратом к столу. При разрезании нож всегда размещался по диагонали квадрата, но Анфисе не всегда удавалось разрезать кусочек пополам, так как плоскость лезвия ножа образовывала двугранный угол [latex]z^o[/latex] с плоскостью основания.
Найти площадь [latex]s[/latex] созданного Анфисой сечения.

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

Целые числа [latex]a[/latex], [latex]b[/latex], [latex]z[/latex], не превышающие [latex]90^o[/latex].

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

Площадь [latex]s[/latex] образованного сечения с точностью до трех десятичных знаков.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]3[/latex] [latex]90[/latex]	[latex]8.485[/latex]
2	[latex]2[/latex] [latex]4[/latex] [latex]0[/latex]	[latex]0.000[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex]	[latex]0.501[/latex]
4	[latex]1[/latex] [latex]1[/latex] [latex]100[/latex]	[latex]1.615[/latex]
5	[latex]3[/latex] [latex]10[/latex] [latex]48[/latex]	[latex]6.725[/latex]

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

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std; 

int main() {
    double a, b, z, s;
    cin >> a >> b >> z;
    if ((1 / (tan (z * M_PI / 180)) > a / sqrt(2) / b) && (z != 0) && (z != 90)){
        s = a * a / 2 / cos (z * M_PI / 180);
    }
    else if (z == 0) {
        s = 0;
    }
    else if (z == 90) {
        s = a * b * sqrt(2);
    }
    else {
        s = (a * sqrt(2) - b * 1 / (tan (z * M_PI / 180))) * b / sin (z * M_PI / 180);
    }
    cout << setprecision(3) << fixed << s;
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double a, b, z, s;

cin >> a >> b >> z;

if ((1 / (tan (z * M_PI / 180)) > a / sqrt(2) / b) && (z != 0) && (z != 90)){

s = a * a / 2 / cos (z * M_PI / 180);

}

else if (z == 0) {

s = 0;

}

else if (z == 90) {

s = a * b * sqrt(2);

}

else {

s = (a * sqrt(2) - b * 1 / (tan (z * M_PI / 180))) * b / sin (z * M_PI / 180);

}

cout << setprecision(3) << fixed << s;

return 0;

}

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

Для решения данной задачи нам нужно рассмотреть 4 случая:
1) Если [latex]\cot[/latex] заданного угла не будет превышать [latex]\frac{a} {\sqrt{2} \cdot b}[/latex] и также не будет равен [latex]0^o[/latex] и [latex]90^o[/latex], то фигурой сечения получится треугольник. Его площадь мы сможем найти по формуле [latex]s = \frac {a^{2}} {2 \cos (z \cdot \frac {\pi} {180})}[/latex].
2) Заданный угол = [latex]0^o[/latex], следовательно площадь сечения также будет = 0, так как сыр нормально и не порежут.
3) Заданный угол = [latex]90^o[/latex], фигурой сечения будет прямоугольник, площадь которого мы сможем найти по формуле [latex]s = a \cdot b \cdot \sqrt{2}[/latex].
4) В любом другом случае, получится трапеция, площадь которой мы найдем по формуле [latex]s = \frac {a \cdot \sqrt{2} — b \cdot 1} {tan(z \cdot \frac{\pi}{180})} \cdot \frac {b} {sin (z \cdot \frac {\pi}{180})}[/latex].

Ссылки

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

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

Related Images:

e-olymp 49. Кот учёный

09/05/2018 by Костя Григорян

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

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

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

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

Вывести день, на который у кота появится чувство голода.

Тесты

Входные данные	Выходные данные
[latex]4\, 4\, 2[/latex]	[latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex]	[latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex]	[latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

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

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int l, n, k, count=0;
    cin >> l >> n >> k;
    for(int i=0; i<n; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)
            count++;
        else
        {
            int a, b, c;
            int deltaX=x2-x1;
            int deltaY=y2-y1;
            a=deltaY;
            b=-deltaX;
            c=y1*deltaX-x1*deltaY;
            if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))
                count++;
        }
    }
    cout << count/k+1 << endl; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int l, n, k, count=0;

cin >> l >> n >> k;

for(int i=0; i<n; i++)

{

int x1, y1, x2, y2;

cin >> x1 >> y1 >> x2 >> y2;

if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)

count++;

else

{

int a, b, c;

int deltaX=x2-x1;

int deltaY=y2-y1;

a=deltaY;

b=-deltaX;

c=y1*deltaX-x1*deltaY;

if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))

count++;

}

cout << count/k+1 << endl;

return 0;

}

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

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 76. Новый шкаф

15/02/2018 by Томас Пасенченко

Задача

Заданы размеры прямоугольной двери [latex]a[/latex], [latex]b[/latex] и размеры шкафа, который имеет форму прямоугольного параллелепипеда [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Можно ли пронести шкаф сквозь дверь, если проносить его разрешается так, чтобы каждое ребро шкафа было параллельно или перпендикулярно стороне двери.

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

Пять действительных чисел [latex]a[/latex], [latex]b[/latex], [latex]x[/latex], [latex]y[/latex], [latex]z[/latex] ( [latex] 0\;\lt\;a,\;b,\;x,\;y,\;z\;\lt\;10[/latex] ).

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

Вывести [latex]1[/latex], если шкаф можно свободно пронести сквозь дверь и [latex]0[/latex] в противоположном случае.

Тесты

Входные данные	Выходные данные
[latex]5\;7\;4\;6\;8[/latex]	[latex]1[/latex]
[latex]1\;4\;2\;3\;6[/latex]	[latex]0[/latex]
[latex]2.9\;6.7\;5.1\;3.7\;1.0[/latex]	[latex]1[/latex]
[latex]4\;6\;6\;4\;3[/latex]	[latex]1[/latex]
[latex]1.5\;8\;9.9\;2\;7.5[/latex]	[latex]0[/latex]
[latex]2\;2\;2\;2\;2[/latex]	[latex]0[/latex]
[latex]2\;3\;7\;8\;8[/latex]	[latex]0[/latex]
[latex]5\;6\;2\;4\;3.5[/latex]	[latex]1[/latex]

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

#include <iostream>
using namespace std;
 
int main() {
    // Новый шкаф
    double a, b, x, y, z;
    cin >> a >> b >> x >> y >> z;
    if ((x < a && y < b) || (y < a && x < b) || (y < a && z < b) || 
    (z < a && y < b) || (x < a && z < b) || (z < a && x < b)) {
        cout << 1;
    } else {
        cout << 0;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

// Новый шкаф

double a, b, x, y, z;

cin >> a >> b >> x >> y >> z;

if ((x < a && y < b) || (y < a && x < b) || (y < a && z < b) ||

(z < a && y < b) || (x < a && z < b) || (z < a && x < b)) {

cout << 1;

} else {

cout << 0;

}

return 0;

}

Решение

Шкаф можно пронести через дверь тогда и только тогда, когда ширина и высота его грани, параллельной дверному проему, меньше ширины и высоты двери.

Имеем шесть возможных вариантов ширины и высоты грани шкафа — [latex](x,y)[/latex], [latex](y,x)[/latex], [latex](y,z)[/latex], [latex](z,y)[/latex], [latex](x,z)[/latex], [latex](z,x)[/latex]

Сравнивая их с размерами двери определяем, можно ли пронести шкаф сквозь дверь.

Ссылки

Условия задачи на e-olymp
Код задачи на ideone

Related Images:

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

26/01/2018 by Мороз Дима

Пример первого теста на графике

На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной окружности, то любые три из них не коллинеарны, и поэтому образуют треугольник. Вам необходимо вычислить суммарную площадь всех этих $C_{n}^3$ треугольников.

Входные данные
Состоит из не более чем $16$ тестов. Каждый тест начинается двумя целыми числами $n \left(0 ≤ n ≤ 500\right)$ и $r \left(0 < r ≤ 100\right)$. Через $n$ обозначено количество точек, а через $r$ радиус окружности. Центр окружности находится в центре координат. Дальше следуют $n$ строк, каждая из которых содержит действительное число $θ \left(0 ≤ θ < 360 \right)$, которое определяет угол в градусах между точкой и направлением $x$-оси. Например, если $θ$ равно $30$ градусов, то соответствующая точка имеет декартовы координаты $\left(r \cdot \cos(30°), r \cdot \sin(30°) \right)$. Последняя строка содержит $n = r = 0$ и не обрабатывается.

Выходные данные
Для каждого теста в отдельной строке вывести целое число — суммарную площадь (округленную до ближайшего целого) всех возможных треугольников, образованных заданными $n$ точками.

Тесты

Входные данные	Выходные данные
5 10 10 100 300 310 320 3 20 10 100 300 0 0	286 320
3 5 25 176 243 0 0	25
4 20 30 80 130 330 0 0	822
2 7 30 230 0 0	0

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

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

int main(){
    double ang, s, sq, r2, res, M[500];
    int n, r, pts;
    while(cin >> n >> r, n + r != 0){
        for(int i = 0; i < n; i++){
                cin >> M[i];
                M[i] = M[i] * M_PI / 180;
        }
        sort(M, M + n);
        res = M_PI * r * r * n * (n - 1) * (n - 2) / 6;
        r2 = r * r / 2.0;
        sq = M_PI * r * r;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                ang = M[j] - M[i];
                if(ang < M_PI){
                        s = r2 * (ang - sin(ang));
                }else{
                    ang = 2 * M_PI - ang;
                    s = sq - r2 * (ang - sin(ang));
                }
                pts = n - (j - i + 1);
                res = res - s * pts;
                pts = n - 2 - pts;
                res = res - (sq - s) * pts;
            }
        }
        printf("%.f\n", res);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdio.h>

using namespace std;

int main(){

double ang, s, sq, r2, res, M[500];

int n, r, pts;

while(cin >> n >> r, n + r != 0){

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

cin >> M[i];

M[i] = M[i] * M_PI / 180;

}

sort(M, M + n);

res = M_PI * r * r * n * (n - 1) * (n - 2) / 6;

r2 = r * r / 2.0;

sq = M_PI * r * r;

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

for(int j = i + 1; j < n; j++){

ang = M[j] - M[i];

if(ang < M_PI){

s = r2 * (ang - sin(ang));

}else{

ang = 2 * M_PI - ang;

s = sq - r2 * (ang - sin(ang));

}

pts = n - (j - i + 1);

res = res - s * pts;

pts = n - 2 - pts;

res = res - (sq - s) * pts;

}

printf("%.f\n", res);

}

return 0;

}

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

Радианная мера точек заносится в массив, после чего массив сортируется по возрастанию с помощью функции sort().

В переменную res изначально заносится площадь, равная площади кругов радиуса $r$,
то есть значение $C_{n}^3 \cdot \pi \cdot r^2 = n(n-1)(n-2)(n-2)\pi \cdot \frac{r^2} {6}$. Значение $\frac{r^2} {2}$ присваивается переменной r2, а sq – площадь одного круга, то есть $\pi \cdot r^2$.

Перебираются пары точек, а затем вычисляется угол.
Если угол меньше, то проходимся по меньшему сегменту, площадь которого равна $\pi r^2-0.5r^2(\alpha-\sin \alpha)$, $\alpha = 2\pi -\alpha$. В ином случае мы проходим по большему сегменту.
В любом случае переменной s присваивается площадь сегмента, который мы проходим от $P_{i}$ к $P_{j}$ при движении против часовой стрелки.

Количество точек, лежащих на сегменте, равно $n-(j-i+1)$.
Значит, из переменной res необходимо вычесть площадь сегмента s такое количество раз, которому равно количество точек, то есть pts .

Количество точек, которые лежат на сегменте площади s , равно $n-2- $ pts.
Площадь противоположного сегмента равна разности площади круга и сегмента. Для получения ответа вычитаем площадь противоположного сегмента из переменной res такое количество раз, которое равно значению переменной pts и выводим полученное значение.

Ссылки

Условие задачи на e-olymp.com
Решение задачи ideone.com

Related Images:

e-olymp 12. Поврежденная картина

13/01/2018 by Андрей Святозар Чернецкий

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

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

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

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

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные	Выходные данные
1 1 6 1 4 0 4 5 6	4.000
0 0 6 0 2 0 5 0 5	2.397
2 0 5 0 0 0 6 0 5	4.172
0 0 5 0 2 0 6 0 1	2.058
0 0 10 0 2 0 6 0 1	0.000

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

struct t {
    double x, y;
    t() {
        x = 0;
        y = 0;
    }
    t(double x, double y) {
        this->x = x;
        this->y = y;
    }
    t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }
        
    t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

    bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

    bool operator!=(t &p) { return !(*this == p); }

    bool t_is_line_segment(t &t1, t &t2) {
        t t3 = *this;
        t a = t2 - t1;
        t b = t3 - t1;
        double sa = a.x * b.y - b.x * a.y;
        if (sa > 0.0) return false;
        if (sa < 0.0) return false;
        if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;
        if (a.length() < b.length()) return false;
        if (t1 == t3) return false;
        if (t2 == t3) return false;
        return true;
    }
    double distance(const t &p) {
        double a = this->x - p.x;
        double b = this->y - p.y;
        return sqrt(a * a + b * b);
    }

    double length(void) { return sqrt(x * x + y * y); }
};

struct line {
    double a, b, c;
    line(const t &t1, const t &t2) {
    a = t1.y - t2.y;
    b = t2.x - t1.x;
    c = t1.x * t2.y - t2.x * t1.y;
    }
};

bool intersect(const line &l1, const line &l2, t &res) {
    if (l1.a * l2.b == l2.a * l1.b)
    return false;
    double g = l1.a * l2.b - l2.a * l1.b;
    res.x = -(l1.c * l2.b - l2.c * l1.b) / g;
    res.y = -(l1.a * l2.c - l2.a * l1.c) / g;
    return true;
}

int main() {

    t x0, x1, x2, x3, m; // m точка пересечения

    double h = 6, answer = 0;

    cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;
    double x0x1_d = x0.distance(x1);
    if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {
        if (x0.t_is_line_segment(x2, x3)) {
            if (x1.t_is_line_segment(x2, x3)) {
                if (x0x1_d <= h) {
                    answer = M_PI * x0x1_d/2;
                } else {
                    answer = x0x1_d * asin(h / x0x1_d);
                }
            } else {
                if (x2.t_is_line_segment(x1, x3)) { 
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));
                                            }
                                } else {
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));
                                            }
                }
            }
        } else {
            double a;
            if (x1.t_is_line_segment(x2, x3)) {
                a = min(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * acos(a / x0x1_d);
                } else {
                    answer = x0x1_d * asin(a / x0x1_d);
                }
            } else {
                a = max(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));
                }
            }
        }
    } else {
        line l10(x0, x1), l23(x2, x3);
        if (intersect(l10, l23, m)) {
            if (m.t_is_line_segment(x2, x3)) {
                double x0m_d = m.distance(x0);
                answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);
                if (answer > h) answer = h;
            }
        }
    }
    cout << fixed << setprecision(3) << answer << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <cmath>

#include <iomanip>

#include <iostream>

using namespace std;

struct t {

double x, y;

t() {

x = 0;

y = 0;

}

t(double x, double y) {

this->x = x;

this->y = y;

}

t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }

t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

bool operator!=(t &p) { return !(*this == p); }

bool t_is_line_segment(t &t1, t &t2) {

t t3 = *this;

t a = t2 - t1;

t b = t3 - t1;

double sa = a.x * b.y - b.x * a.y;

if (sa > 0.0) return false;

if (sa < 0.0) return false;

if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;

if (a.length() < b.length()) return false;

if (t1 == t3) return false;

if (t2 == t3) return false;

return true;

}

double distance(const t &p) {

double a = this->x - p.x;

double b = this->y - p.y;

return sqrt(a * a + b * b);

}

double length(void) { return sqrt(x * x + y * y); }

};

struct line {

double a, b, c;

line(const t &t1, const t &t2) {

a = t1.y - t2.y;

b = t2.x - t1.x;

c = t1.x * t2.y - t2.x * t1.y;

}

};

bool intersect(const line &l1, const line &l2, t &res) {

if (l1.a * l2.b == l2.a * l1.b)

return false;

double g = l1.a * l2.b - l2.a * l1.b;

res.x = -(l1.c * l2.b - l2.c * l1.b) / g;

res.y = -(l1.a * l2.c - l2.a * l1.c) / g;

return true;

}

int main() {

t x0, x1, x2, x3, m; // m точка пересечения

double h = 6, answer = 0;

cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;

double x0x1_d = x0.distance(x1);

if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {

if (x0.t_is_line_segment(x2, x3)) {

if (x1.t_is_line_segment(x2, x3)) {

if (x0x1_d <= h) {

answer = M_PI * x0x1_d/2;

} else {

answer = x0x1_d * asin(h / x0x1_d);

}

} else {

if (x2.t_is_line_segment(x1, x3)) {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));

}

} else {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));

}

} else {

double a;

if (x1.t_is_line_segment(x2, x3)) {

a = min(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * acos(a / x0x1_d);

} else {

answer = x0x1_d * asin(a / x0x1_d);

}

} else {

a = max(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));

}

} else {

line l10(x0, x1), l23(x2, x3);

if (intersect(l10, l23, m)) {

if (m.t_is_line_segment(x2, x3)) {

double x0m_d = m.distance(x0);

answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);

if (answer > h) answer = h;

}

cout << fixed << setprecision(3) << answer << endl;

return 0;

}

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

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]H[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]H[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]H[/latex]

в таком случае нам необходимо найти дугу [latex]NX_1[/latex],для этого умножив радиус на величину центрального угла: [latex]NX_1[/latex] =[latex]X_0 X_1 \times \arcsin \frac {H}{X_0 X_1}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1.[latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1. [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times \arcsin \frac{X_0 X_3} {X_0 X_1} [/latex]

1.1.2.1.2. [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

1.1.2.1.2.1. [latex]X_0 X_1 < \sqrt{X_0 X_2^2 + H^2} [/latex]

В таком случае искомая величина равна дуге [latex]MN[/latex]= [latex]X_0 X_1 \times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{X_0 X_3} {X_0 X_1}))

1.1.2.2. данный случай аналогичен предыдущему.Единственное различие заключается в том,что точки [latex]X_2[/latex] и [latex]X_3[/latex] меняются местами в формулах.

1.2 [latex]Х_0[/latex] не принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.2.1 [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times \arccos \frac{A}{X_0 X_1}[/latex]

1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times \arcsin \frac{A}{X_0 X_1}[/latex]

1.2.2. обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.2.2.1. [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{A}{X_0 X_1})[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

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

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

Ссылки

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

Related Images:

e-olymp 143. Точка и треугольник

26/12/2017 by Александра Филистович

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

№	Входные данные	Выходные данные
1	2 6 -9 3 8 1 5 11	1
2	-13 10 -12 5 99 80 17 13	0
3	98 -50 -87 7 5 3 23 17	0
4	5 15 7 12 5 3 2 54	1
5	2 2 3 1 1 3 9 11	1

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

#include <iostream>
using namespace std;
 
int main() {
 double x0,x1,x2,x3,y0,y1,y2,y3;
 double z1,z2,z3;
 cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
 z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);
 z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);
 z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);
 if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";
 else cout<<"0";
 return 0;
}

#include <iostream>

using namespace std;

int main() {

double x0,x1,x2,x3,y0,y1,y2,y3;

double z1,z2,z3;

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

z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);

z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);

z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);

if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";

else cout<<"0";

return 0;

}

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

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].