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 7213. Шашка на кубе

12/12/2020 by Максим Ливитчук

Условие

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

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

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

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

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

Вывести искомое количество способов.

Тесты

l	m	вывод
3	3	1
3	4	0
3	5	25
51	199	4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3	199	11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

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

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}
#define SIDENUM 3 //количество сторон куба которые хранятся
#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
        v.push_back(s);
    }
    void print() { //вывод числа
        cout <<(v.empty() ? 0 : v.back());
        for (int i = (int)v.size() - 2; i>=0; i--)
            cout <<setfill('0') <<setw(DNUM) <<v[i];
    }
    void add(LongNum term) { //прибавление длинного числа
        auto b = term.v;
        int carry = 0;
        for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
            if (i == v.size())
                v.push_back(0);
            v[i] += carry + (i < b.size() ? b[i] : 0);
            carry = v[i] >= BASE;
            if (carry)  v[i] -= BASE;
        }
    }
};

struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
};

struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
};

CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
        switch(side) {
        //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
        //обнуляя y, а в x записывает старый y 
        cr(0, 1, y,     0); //и так далее
        cr(1, 1, l-1,   y);
        cr(2, 1, l-y-1, l-1);
        }
    } else if(x == l) {//правее
        switch(side) {
        cr(0, 1, l-y-1, 0);
        cr(1, 1, 0,     y);
        cr(2, 1, y,     l-1);
        }
    } else if(y == -1) {//выше
        switch(side) {
        cr(0, 1, l-x-1, 0);
        cr(1, 0, x,     l-1);
        cr(2, 1, x,     l-1);
        }
    } else if(y == l) {//ниже
        switch(side) {
        cr(0, 1, x,     0);
        cr(1, 2, x,     0);
        cr(2, 1, l-x-1, l-1);
        }
    } else {
        // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
        return CellCoord{side, x, y};
    }
}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
        FixNeighbor(l, side, x-1, y),
        FixNeighbor(l, side, x+1, y),
        FixNeighbor(l, side, x, y-1),
        FixNeighbor(l, side, x, y+1)
    }};
}

int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
        for(short xi=0; xi<l; xi++) {
            for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
                nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
                //кэш координат соседних клеток
            }
        }
    }

    for(short i=0; i<m; i++) {
        for(short side=0; side<SIDENUM; side++) {
            for(short xi=0; xi<l; xi++) {
                for(short yi=0; yi<l; yi++) { //перебор всех клеток
                    LongNum neighbor_sum;
                    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
                        neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
                        //сложение количества путей ко всем соседям на предыдущем шаге
                    }
                    cubes[!flag][side][xi][yi] = neighbor_sum;
                    //запись получившейся суммы в клетку
                }
            }
        }
        flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}

#define SIDENUM 3 //количество сторон куба которые хранятся

#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики

#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {

//реализация длинной арифметики на векторах со сложением и выводом

vector<int> v;

LongNum() {} //стандартный конструктор

LongNum(int s) { //конструктор из int

v.push_back(s);

}

void print() { //вывод числа

cout <<(v.empty() ? 0 : v.back());

for (int i = (int)v.size() - 2; i>=0; i--)

cout <<setfill('0') <<setw(DNUM) <<v[i];

}

void add(LongNum term) { //прибавление длинного числа

auto b = term.v;

int carry = 0;

for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {

if (i == v.size())

v.push_back(0);

v[i] += carry + (i < b.size() ? b[i] : 0);

carry = v[i] >= BASE;

if (carry) v[i] -= BASE;

}

};

struct CellCoord {

//хранит данные о положении клетки

short side;

short x, y;

};

struct CellNeighbors {

//хранит данные о положении всех(4) соседей определённой клетки

CellCoord n[4];

};

CellCoord FixNeighbor(short l, short side, short x, short y) {

//исправляет данные о положении клетки, если она выходит за края грани

if(x == -1) { //если сосед находится левее грани

switch(side) {

//если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,

//обнуляя y, а в x записывает старый y

cr(0, 1, y, 0); //и так далее

cr(1, 1, l-1, y);

cr(2, 1, l-y-1, l-1);

}

} else if(x == l) {//правее

switch(side) {

cr(0, 1, l-y-1, 0);

cr(1, 1, 0, y);

cr(2, 1, y, l-1);

}

} else if(y == -1) {//выше

switch(side) {

cr(0, 1, l-x-1, 0);

cr(1, 0, x, l-1);

cr(2, 1, x, l-1);

}

} else if(y == l) {//ниже

switch(side) {

cr(0, 1, x, 0);

cr(1, 2, x, 0);

cr(2, 1, l-x-1, l-1);

}

} else {

// если координаты не вышли за границы грани просто возвращаем неизменёные координаты

return CellCoord{side, x, y};

}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {

//возвращает исправленные координаты всех(4) соседних клеток

return CellNeighbors{{

FixNeighbor(l, side, x-1, y),

FixNeighbor(l, side, x+1, y),

FixNeighbor(l, side, x, y-1),

FixNeighbor(l, side, x, y+1)

}};

}

int main() {

short l, m;

bool flag = false;

cin >>l >>m;

LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

cubes[0][0][l/2][l/2] = LongNum(1);

//за 0 ходов можно дойти 1 путём в изначальную точку

CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];

//массив координат соседей

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор координат всех клеток

nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);

//кэш координат соседних клеток

}

for(short i=0; i<m; i++) {

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор всех клеток

LongNum neighbor_sum;

for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей

neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);

//сложение количества путей ко всем соседям на предыдущем шаге

}

cubes[!flag][side][xi][yi] = neighbor_sum;

//запись получившейся суммы в клетку

}

flag = !flag; //замена местами массива для предыдущего шага и нынешнего

}

cubes[flag][1][l/2][l/2].print();

//вывод количества путей к центру соседней грани на m-ом шаге

}

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

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

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

Ссылки

Related Images:

e-olymp 4752. Кинотеатр

21/05/2019 by Андрей Зиновьев

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

Входные данные:
В первой строке заданы числа $n$ и $m$ $(1 \le n, \le 1000)$.

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

Тесты

Входные данные	Вывод программы
3 3	3
3 2	2
231 543	3

Continue reading →

Related Images:

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

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

Задача

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

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

В первой строке находится количество синих квадратов $n$ ($0 < n < 40404$). Далее идут $n$ строк, каждая из которых содержит координаты $x$, $y$ ($-101 \leq x, y \leq 101$) левых нижних углов синих квадратов.

Каждый синий квадрат имеет хотя бы одну общую точку хотя бы с одним другим синим квадратом. Фигура, образованная синими квадратами, является связной.

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

Вывести количество красных квадратов.

Тесты

Входные данные	Выходные данные
$3$ $1$ $2$ $2$ $1$ $3$ $1$	$3$
$3$ $1$ $1$ $2$ $2$ $1$ $3$	$6$
$10$ $1$ $1$ $2$ $2$ $1$ $3$ $2$ $4$ $1$ $5$ $2$ $6$ $1$ $7$ $2$ $8$ $1$ $9$ $2$ $10$	$90$

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

#include <iostream>
using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

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

#include <iostream>

using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {

int n;

cin >> n;

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

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

}

int perimiter = 0;

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

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

if (squares[i][j]){

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

}

int max = 0;

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

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

if (i * j - n > max) {

max = i * j - n;

}

cout << max;

return 0;

}

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

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

Чтобы доказать это, пусть сторона квадрата равна $1$. Тогда периметр фигуры, составленной из этих квадратов, всегда будет делится на $2$ (это легко понять, строя такие фигуры на листке бумаги: добавление каждого нового квадрата в фигуру может изменить периметр только на $-4, -2, 0, 2, 4$). А так как периметр прямоугольника равен $2 * (a + b)$, где $a, b$ – стороны прямоугольника, то для существования прямоугольника с таким-же периметром должно выполняться условие $\forall p \in \mathbb{N} , p > 2 \rightarrow \exists a,b \in \mathbb{N} : 2p = 2*( a + b )$. Очевидно, что условие действительно выполняется для всех $p>2$.

Запишем нашу фигуру в массив squares. После чего посчитаем ее периметр: каждый непустой квадратик фигуры добавляет $1$ к периметру за каждую пустую клеточку слева, справа, сверху или снизу от него. Далее будем искать все подходящие прямоугольники, записывая максимальную площадь в переменную max: перебирая значения первой стороны $j$, высчитываем через периметр вторую сторону $i = \displaystyle \frac{p}{2} — j$. Площадь будем считать, как разницу площади прямоугольника и изначальной фигуры (число $n$ равно площади фигуры, потому что площадь каждого квадрата равна $1$).
В конце, выводим разницу максимальной площади и площади изначальной фигуры (площадь изначальной фигуры равна $n$, ведь площадь каждого квадрата равна $1$).

Ссылки

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

Related Images:

e-olymp 72. Дорога домой

26/12/2017 by Павел Жуков

Задача

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]left langle 1,1 right rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.

Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]left langle 0,0 right rangle[/latex], а его дом расположен в точке [latex]left langle x_{h},y_{h} right rangle[/latex], и направление движения он менял [latex]k[/latex] раз.

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

В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0leq n,k,t,vleq 100)[/latex] . Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5leq x_{h}, y_{h}leq 10^5)[/latex] .

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

Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.

Тесты

Входные данные	Выходные данные
[latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex] [latex]5[/latex] [latex]7[/latex]	Good night Ia
[latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex] [latex]15[/latex] [latex]15[/latex]	Good night Ia
[latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex] [latex]105[/latex] [latex]-105[/latex]	Poor Ia
[latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex] [latex]40[/latex] [latex]-20[/latex]	Good night Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-24[/latex] [latex]0[/latex]	Poor Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-23[/latex] [latex]0[/latex]	Good night Ia

Первый вариант кода программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long int n, k, t, v, hx, hy;
    long int x = 0, y = 0;
    cin >> n >> k >> t >> v;
    cin >> hx >> hy;
    for(long int i = 0; i <= k; i++){
         if(i%4 == 0){ 
             x += 1 + n*i;
             y += 1 + n*i; 
         } else if (i%4 == 1){ 
             x += 1 + n*i;
             y -= 1 + n*i; 
         } else if(i%4 == 2){
             x -= 1 + n*i; 
             y -= 1 + n*i; 
         } else if(i%4 == 3){ 
             x -= 1 + n*i; 
             y += 1 + n*i; 
         } 
    } 
    if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

long int x = 0, y = 0;

cin >> n >> k >> t >> v;

cin >> hx >> hy;

for(long int i = 0; i <= k; i++){

if(i%4 == 0){

x += 1 + n*i;

y += 1 + n*i;

} else if (i%4 == 1){

x += 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 2){

x -= 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 3){

x -= 1 + n*i;

y += 1 + n*i;

}

if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

Второй вариант кода программы

#include <iostream>
using namespace std;

int main() {
    long int n, k, t, v, hx, hy;
    cin >> n >> k >> t >> v >> hx >> hy;
    long int s1, s2, s3, s4;
    long int m1, m2, m3, m4;
    m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m4 = (k + 1) / 4;
    s1 = (1 + (m1 - 1) * 2 * n) * m1;
    s2 = (1 + n + 2 * n * (m2 - 1)) * m2;
    s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;
    s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;
    long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;
    if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

cin >> n >> k >> t >> v >> hx >> hy;

long int s1, s2, s3, s4;

long int m1, m2, m3, m4;

m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m4 = (k + 1) / 4;

s1 = (1 + (m1 - 1) * 2 * n) * m1;

s2 = (1 + n + 2 * n * (m2 - 1)) * m2;

s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;

s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;

long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;

if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

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

Вариант 1

Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]sumlimits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:

[latex]f(x,y) = begin{cases} left langle1 + xy, 1 + xyright rangle & textit{if } xvdots 4 = 0 \ left langle1 + xy, (-1) cdot (1 + xy)right rangle & textit{if } xvdots 4 = 1 \ left langle(-1) cdot (1 + xy), (-1) \cdot (1 + xy)right rangle & textit{if } xvdots 4 = 2 \ left langle(-1) cdot (1 + xy), 1 + xyright rangle & textit{if } xvdots 4 = 3 end{cases}[/latex]

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]sumlimits_{i=0}^k f(i, n)[/latex] — это вектор [latex]left langle a,b right rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]left langle a,b right rangle[/latex] и вектора [latex]left langle x_{h},y_{h} right rangle[/latex]:

$$sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$

И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]left langle 0,0 right rangle[/latex] и [latex]left langle 1,1 right rangle[/latex], то есть — [latex]sqrt{2}[/latex].

$$ sqrt{2} tv$$

Итого, выводим Good night Ia, если [latex]2t^2v^2 geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.

Вариант 2

Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = displaystylefrac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$

Для направления на северо-восток:
$$a_1 = 1, d = 4n Rightarrow S_{1}=frac{1 + 1 +4n(m_1-1)}{2}Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=1$ иначе, $m_1=displaystylefrac{k+1}{4}$

Для направления на юго-восток:
$$a_2 = 1+n, d = 4n Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=2$ иначе, $m_2=displaystylefrac{k+1}{4}$

Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=3$ иначе, $m_3=displaystylefrac{k+1}{4}$

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=4$ иначе, $m_4=displaystylefrac{k+1}{4}$

Тогда, для вычисления координат [latex]left langle x,y right rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.

Ссылки

Условие задачи на e-olymp
Код решения первого варианта на ideone.com
Код решения второго варианта на ideone.com

Related Images:

e-olymp 74. Паук и муха — 2

16/12/2017 by Алиса Ворохта

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится? Известно, что паук может передвигаться только по поверхности комнаты или же спускаться на паутине с потолка на пол, но только под прямым углом.

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

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

Одно число – расстояние, на которое переместится паук, посчитанное с точностью до 2-х знаков после запятой.

Тесты

Входные данные								Выходные данные
[latex]A[/latex]	[latex]B[/latex]	[latex]C[/latex]	[latex]X1[/latex]	[latex]Y1[/latex]	[latex]X2[/latex]	[latex]Y2[/latex]	[latex]Z2[/latex]	[latex]S[/latex]
[latex]4[/latex]	[latex]7[/latex]	[latex]3[/latex]	[latex]2[/latex]	[latex]1[/latex]	[latex]3[/latex]	[latex]7[/latex]	[latex]2[/latex]	[latex]8.06[/latex]
[latex]145[/latex]	[latex]26[/latex]	[latex]306[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]0[/latex]	[latex]305[/latex]	[latex]309.34[/latex]
[latex]26[/latex]	[latex]18[/latex]	[latex]53[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]24[/latex]	[latex]1[/latex]	[latex]53[/latex]	[latex]58.52[/latex]
[latex]89[/latex]	[latex]89[/latex]	[latex]189[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]89[/latex]	[latex]16[/latex]	[latex]70.77[/latex]
[latex]18[/latex]	[latex]26[/latex]	[latex]145[/latex]	[latex]14[/latex]	[latex]2[/latex]	[latex]17[/latex]	[latex]26[/latex]	[latex]141[/latex]	[latex]147.14[/latex]

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

#include <iostream>
#include <cmath> //подключаем для возможности извлечения корня
#include <iomanip> //подключаем, чтобы округлить до определенного количества знаков
using namespace std;
 
double distance(long long X1, long long Y1, long long X2, long long Y2) 
{
    return sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));
}
int main() {
    long long A, B, C, X1, X2, Y1, Y2, Z2;
    double S = 1000000000;
    cin >> A >> B >> C >> X1 >> Y1 >> X2 >> Y2 >> Z2;
    if (Z2 == 0)
    {
        S = distance(X1, Y1, X2, Y2);
    }
    else
    {
        if (X2 == 0)
        {
            S = min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));
            S = min(S, distance(X1, Y1, Y2 - B, B + Z2));
        }
        if (X2 == A)
        {
            S = min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));
            S = min(S, distance(X1, Y1, A + B - Y2, Z2 + B));
        }
        if (Y2 == 0)
        {
            S = min(S, distance(X1, Y1, X2, -Z2));
            S = min(S, distance(X1, Y1, -Z2, -X2));
            S = min(S, distance(X1, Y1, A + Z2, X2 - A));
        }
        if (Y2 == B)
        {
            S = min(S, distance(X1, Y1, X2, Z2 + B));
            S = min(S, distance(X1, Y1, -Z2, X2 + B));
            S = min(S, distance(X1, Y1, A + Z2, B + A - X2));
        }
        if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))
        {
            S = min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));
            S = min(S, distance(X1, Y1, X2, 2*B - Y2 + C));
            S = min(S, distance(X1, Y1, -X2 - C, Y2));
            S = min(S, distance(X1, Y1, 2*A - X2 + C, Y2));
            S = min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));
            S = min(S, distance(X1, Y1, A + C + Y2, X2 - A));
            S = min(S, distance(X1, Y1, -C - Y2, -X2));
            S = min(S, distance(X1, Y1, Y2 - B - C, B + X2));
            S = min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));
            S = min(S, distance(X1, Y1, Y2 - B, B + C + X2));
            S = min(S, distance(X1, Y1, -Y2, -C - X2));
            S = min(S, distance(X1, Y1, A + Y2, -A - C + X2));
        }
    }
    cout << fixed << setprecision(2) << S;
    return 0;
}

#include <iostream>

#include <cmath> //подключаем для возможности извлечения корня

#include <iomanip> //подключаем, чтобы округлить до определенного количества знаков

using namespace std;

double distance(long long X1, long long Y1, long long X2, long long Y2)

{

return sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));

}

int main() {

long long A, B, C, X1, X2, Y1, Y2, Z2;

double S = 1000000000;

cin >> A >> B >> C >> X1 >> Y1 >> X2 >> Y2 >> Z2;

if (Z2 == 0)

{

S = distance(X1, Y1, X2, Y2);

}

else

{

if (X2 == 0)

{

S = min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));

S = min(S, distance(X1, Y1, Y2 - B, B + Z2));

}

if (X2 == A)

{

S = min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));

S = min(S, distance(X1, Y1, A + B - Y2, Z2 + B));

}

if (Y2 == 0)

{

S = min(S, distance(X1, Y1, X2, -Z2));

S = min(S, distance(X1, Y1, -Z2, -X2));

S = min(S, distance(X1, Y1, A + Z2, X2 - A));

}

if (Y2 == B)

{

S = min(S, distance(X1, Y1, X2, Z2 + B));

S = min(S, distance(X1, Y1, -Z2, X2 + B));

S = min(S, distance(X1, Y1, A + Z2, B + A - X2));

}

if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))

{

S = min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));

S = min(S, distance(X1, Y1, X2, 2*B - Y2 + C));

S = min(S, distance(X1, Y1, -X2 - C, Y2));

S = min(S, distance(X1, Y1, 2*A - X2 + C, Y2));

S = min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));

S = min(S, distance(X1, Y1, A + C + Y2, X2 - A));

S = min(S, distance(X1, Y1, -C - Y2, -X2));

S = min(S, distance(X1, Y1, Y2 - B - C, B + X2));

S = min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));

S = min(S, distance(X1, Y1, Y2 - B, B + C + X2));

S = min(S, distance(X1, Y1, -Y2, -C - X2));

S = min(S, distance(X1, Y1, A + Y2, -A - C + X2));

}

cout << fixed << setprecision(2) << S;

return 0;

}

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

Данная задача решается с помощью «разверток» комнаты: переход от трёхмерного пространства к двумерному.
Вид комнаты:

Рассмотрим такие случаи:

Паук находится на полу ([latex]Z_2 = 0[/latex]);
Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex] с помощью функции [latex]distance[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

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

По этим разверткам мы можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex]. Если же паук находится в одном из углов комнаты, то мы находим наименьшее расстояние из двух вариантов развертки.
Когда же паук сидит на потолке, не соприкасаясь ни с одной из стенок, у него есть 13 вариантов:

Паук спускается с потолка на паутине, затем ползет точно так же, как и в самом первом случае.
Паук ползет по потолку, по одной из стенок и по полу. Тогда развертка будет выглядеть следующим образом (потолок можно развернуть в 4 стороны — отсюда 4 случая):
Паук ползет по потолку, а затем по двум соседним стенкам и по полу. Таких случаев 8, поскольку порядок следования стенок, по которым тот ползет, также важен. Развертка одного из них:

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex].

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

Related Images:

e-olymp 61. Уборка снега

13/12/2017 by Кирилл Волков

Задача

Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?

При этом известно, что:

Снегоход может очищать только одну проезжую полосу дороги за один проход.
Все дороги прямые с одной полосой движения в каждом направлении.
Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
Во время очистки снега снегоход двигается со скоростью $20$ км/час, и со скоростью $50$ км/час по уже очищенной дороге.
Возможность проехать все дороги всегда существует.

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

Первая строка содержит два числа $x$ и $y$ $(-30000 ≤ x, y ≤ 30000)$ — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

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

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

Тесты

Входные данные	Выходные данные
$0$ $0$ $0$ $0$ $-1000$ $2000$ $0$ $0$ $1000$ $2000$	$0:27$
$0$ $1000$ $0$ $0$ $0$ $3000$ $0$ $0$ $1000$ $1000$ $0$ $0$ $3000$ $0$ $3000$ $0$ $3000$ $3000$ $3000$ $3000$ $0$ $3000$ $0$ $3000$ $1000$ $2000$ $3000$ $0$ $2000$ $1000$ $3000$ $3000$ $2000$ $2000$	$1:46$
$-500$ $0$ $-1000$ $0$ $0$ $0$ $0$ $0$ $1000$ $0$ $-1000$ $1000$ $0$ $0$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$ $1000$ $1000$ $0$ $1000$ $0$ $1000$ $0$ $0$	$0:49$
$1000$ $500$ $-1000$ $0$ $1000$ $0$ $-1000$ $1000$ $1000$ $1000$ $-1000$ $0$ $-1000$ $1000$ $1000$ $0$ $1000$ $1000$ $-1000$ $0$ $1000$ $1000$ $1000$ $0$ $-1000$ $1000$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$	$1:20$
$500$ $-500$ $0$ $0$ $1000$ $-1000$ $1000$ $-1000$ $2000$ $0$ $2000$ $0$ $3000$ $-1000$ $3000$ $-1000$ $4000$ $0$ $4000$ $0$ $5000$ $-1000$ $5000$ $-1000$ $6000$ $0$ $0$ $0$ $8000$ $0$	$1:39$

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

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

int main() {
    double temp;
    cin >> temp >> temp;
    double lengthOfRoads = 0;
    double firstX, firstY, secondX, secondY;
    while (cin >> firstX >> firstY >> secondX >> secondY)
    {
        lengthOfRoads += sqrt((secondX - firstX)*(secondX - firstX)+(secondY - firstY)*(secondY - firstY));
    }
    int minutes = round(3 * lengthOfRoads / 500);
    cout<< minutes / 60 << ":" << minutes % 60;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double temp;

cin >> temp >> temp;

double lengthOfRoads = 0;

double firstX, firstY, secondX, secondY;

while (cin >> firstX >> firstY >> secondX >> secondY)

{

lengthOfRoads += sqrt((secondX - firstX)*(secondX - firstX)+(secondY - firstY)*(secondY - firstY));

}

int minutes = round(3 * lengthOfRoads / 500);

cout<< minutes / 60 << ":" << minutes % 60;

return 0;

}

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

Начало пути всегда находится на одной из данных дорог. Составим оптимальный алгоритм движения снегохода. По каждой из дорог необходимо проехать в одну и другую сторону. Снегоход может начинать движение в любую сторону. Во время движения ему необходимо двигаться прямо, не разворачиваясь, настолько долго, насколько это возможно. В случае, если на пути следования снегоходу встречается поворот, ему необходимо повернуть и далее работать по тому же алгоритму, принимая за начальную точку точку поворота. После возвращения из поворота снегоход должен продолжить движение по алгоритму. Когда снегоход попадает в тупик, возвращается на перекресток, на котором был совершен поворот или попадает в начальную точку, ему необходимо развернуться и двигаться обратно по той же траектории. По возвращении в начальную точку снегоход должен, в случае необходимости, двигаться во все оставшиеся стороны по такому же алгоритму. Таким образом, при движении по такому алгоритму, снегоход будет проезжать по каждой дороге по одному разу в каждую сторону, то есть не будет нигде проезжать «лишние» километры, следовательно время, за которое снегоход может объехать все дороги по одному разу в каждую сторону и есть искомым. Таким образом нам необходимо посчитать сумму длин всех дорог $L$, координаты начала и конца которых даны во входном потоке. Снегоход всегда двигается со скоростью $V = 20 км/час = \frac{1000}{3}м/мин$. По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах:
$t = \frac{2L}{V} = \frac{3L}{500}$.
Округлив полученное значение $t$ до целых минут и представив это время в виде часов и минут, получаем ответ.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

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

Related Images:

e-olymp 13. Паук и муха

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

Задача

В пустой прямоугольной комнате размерами [latex]A \times B \times C[/latex] (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке — координаты мухи [latex]X_1[/latex], [latex]Y_1[/latex] и паука [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex].

Все входные данные — целые числа, не превышающие 500.

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

Единственное число — расстояние, на которое переместится паук, вычисленное с точностью до 2-х знаков после запятой.

Тесты

Входные данные	Выходные данные
$3$ $4$ $8$ $0$ $0$ $3$ $4$ $0$	$5.00$
$2$ $2$ $8$ $1$ $1$ $2$ $1$ $4$	$5.00$
$6$ $4$ $3$ $5$ $1$ $0$ $2$ $1$	$6.08$
$30$ $60$ $27$ $13$ $21$ $8$ $0$ $17$	$38.33$
$40$ $40$ $40$ $10$ $5$ $8$ $40$ $37$	$72.03$

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

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
double distance (double X1,double X2,double Y1,double Y2)
{
    return (sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)));
}
int main() {
    cout.precision(2);
    double A, B, C;
    cin>>A>>B>>C;
    double X2, Y2, X1, Y1, Z2;
    cin>>X1>>Y1;
    cin>>X2>>Y2>>Z2;
    double s=250000000;
    if (Z2==0) s=distance (X1,X2,Y1,Y2);//"floor" case
    else
    {
        if (X2==0) {X2=-Z2; s=distance (X1,X2,Y1,Y2);}//"left wall" case
        if (X2==A) {X2=A+Z2; s=distance (X1,X2,Y1,Y2);}//"right wall" case
        if (Y2==0) {Y2=-Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"near wall" case
        if (Y2==B) {Y2=B+Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"distant wall" case
    }
    cout<<fixed<<s;
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

double distance (double X1,double X2,double Y1,double Y2)

{

return (sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)));

}

int main() {

cout.precision(2);

double A, B, C;

cin>>A>>B>>C;

double X2, Y2, X1, Y1, Z2;

cin>>X1>>Y1;

cin>>X2>>Y2>>Z2;

double s=250000000;

if (Z2==0) s=distance (X1,X2,Y1,Y2);//"floor" case

else

{

if (X2==0) {X2=-Z2; s=distance (X1,X2,Y1,Y2);}//"left wall" case

if (X2==A) {X2=A+Z2; s=distance (X1,X2,Y1,Y2);}//"right wall" case

if (Y2==0) {Y2=-Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"near wall" case

if (Y2==B) {Y2=B+Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"distant wall" case

}

cout<<fixed<<s;

return 0;

}

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

Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции [latex]distance[/latex].
В простейшем случае, если паук находится на полу комнаты, т.е. его координата [latex]Z_2[/latex] нулевая, координаты паука [latex]X_2[/latex] и [latex]Y_2[/latex] в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции [latex]distance[/latex].
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

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

Related Images:

ML33. Угол между вектором и осями координат

19/09/2016 by Курьянов Павел

Задача

Найдите углы между вектором [latex] \overrightarrow{a}=(x,y,z)[/latex] и координатными осями [latex]Ox, Oy, Oz[/latex].

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

Координаты вектора [latex]\overrightarrow{a}=(x,y,z)[/latex].

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

Угол между заданным вектором и [latex]Ox[/latex].
Угол между заданным вектором и [latex]Oy[/latex].
Угол между заданным вектором и [latex]Oz[/latex].

Тесты

Входные данные			Выходные данные
x	y	z	угол c Ox	угол c Oy	угол c Oz
0	0	1	90	90	0
0	9999.99	0	90	0	90
1	1	1	54.7456	54.7456	54.7456
-9999.5	-9999.5	-9999.5	-54.7456	-54.7456	-54.7456
0	0	0	невозможно при нулевом векторе

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

#include 
#include 
using namespace std;
 
int main() {
  double x,y,z, cosx,cosy,cosz;
  cin>>x>>y>>z;//вводим координаты нашего вектора
    if (x==0 && y==0 && z==0)//проверяем не является ли наш вектор нулевым
    {
      cout<<"Невозможно при нулевом векторе";//если у нас нулевой ветор выводить ошибку
    }
    else
    {
      cosx=x/(sqrt(x*x+y*y+z*z));//при ином условии подсчитываем косинусы углов между вектором и осями координат
      cosy=y/(sqrt(x*x+y*y+z*z));
      cosz=z/(sqrt(x*x+y*y+z*z));
      cout<<acos(cosx)*180/M_PI<<" "<<acos(cosy)*180/M_PI<<" "<<acos(cosz)*180/M_PI;// выводим полученые углы координат в градусах
    }
    return 0;
}

#include

using namespace std;

int main() {

double x,y,z, cosx,cosy,cosz;

cin>>x>>y>>z;//вводим координаты нашего вектора

if (x==0 && y==0 && z==0)//проверяем не является ли наш вектор нулевым

{

cout<<"Невозможно при нулевом векторе";//если у нас нулевой ветор выводить ошибку

}

else

{

cosx=x/(sqrt(x*x+y*y+z*z));//при ином условии подсчитываем косинусы углов между вектором и осями координат

cosy=y/(sqrt(x*x+y*y+z*z));

cosz=z/(sqrt(x*x+y*y+z*z));

cout<<acos(cosx)*180/M_PI<<" "<<acos(cosy)*180/M_PI<<" "<<acos(cosz)*180/M_PI;// выводим полученые углы координат в градусах

}

return 0;

}

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

Для начала проверим не является ли заданный вектор нулевым, так как он не будет образовывать угол между векторами. Если это нулевой, то выводить, что это невозможно при нулевом векторе. При другом условии решим задачу,а поскольку в условии нам даны координаты только 1 вектора, а для вычисления угла между 2 векторами нужно 2 пары координат, то будем считать, что [latex] Ox(1,0,0) [/latex], [latex] Oy(0,1,0) [/latex],[latex] Oz(0,0,1) [/latex].
Теперь мы можем вычислить угол между векторами через формулу[latex] \cos{ |\widehat { a,b } }|=\frac { \overrightarrow { a } \overrightarrow { b } }{ \left| \overrightarrow { a } \right| \left| \overrightarrow { b } \right| } [/latex], где [latex] \overrightarrow { a } \overrightarrow { b }=\ x_a\cdot{x_b}+y_a\cdot{y_b}+z_a\cdot{z_b}\[/latex] и [latex] { \left| \overrightarrow { a } \right| }=\sqrt{x_a^2+y_a^2+z_a^2} [/latex], которую можно сократить в соответствии с нашими значениями координат [latex]Ox,Oy,Oz [/latex] и в итоге получаем формулу [latex] \arccos=\frac{o}{\sqrt{x_a^2+y_a^2+z_a^2}} [/latex], где [latex] O [/latex] ось координат и [latex]o [/latex] значение по этой оси координат. В эту формулу поочередно подставляем наши значения и получаем косинусы углов между осями координат и заданным вектором. Для вычисления углов в радианах воспользуемся встроенной функцией [latex] acos [/latex], а для вычисления в градусах домножим полученный результат на 180 и разделим на встроенное значение числа [latex] \pi [/latex].

Ссылки
Ideone

Related Images:

Mif 8

07/10/2015 by Настя Ивасенко

Задача

Условие взято отсюда

Четырёхугольник [latex]ABCD[/latex] задан на плоскости целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Из характеристик указать наиболее частную.

Тесты

[latex]a_1[/latex] [latex]a_2[/latex]	[latex]b_1[/latex] [latex]b_2[/latex]	[latex]c_1[/latex][latex]c_2[/latex]	[latex]d_1[/latex] [latex]d_2[/latex]	Ответ
0 0	1 0	1 1	0 1	квадрат
0 -3	2 0	0 3	-2 0	ромб
0 0	4 0	4 1	1 4	прямоугольник
0 0	10 0	12 4	2 4	пaраллелограмм
0 0	2 0	1 1	0 1	трапеция
0 0	0 2	1 1	1 0	трапеция
-4 -5	-15 7	5 8	6 -7	произвольный
0 0	1 0	10 20	-5 7	произвольный

Код

#include <iostream>
using namespace std;
 
int main() {
	int a1, a2, b1, b2, c1, c2, d1, d2;
	double  AB, BC, CD, DA, AC, BD, A, B, C, D;
	cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;
	AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени
	BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));
	CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));
	DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));
	AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени
	BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));
	if(AB==CD && BC==DA) {
		if (AB==BC){
			if(AC==BD){
				cout << "квадрат";
			}
			else {
				cout << "ромб";
			}
		}
		else 
		if (AC==BD){
			cout<< "прямоугольник";
		}
		else{
			cout << "параллелограмм";
		}
	}
	else 
	if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){
		cout << "трапеция";
	}
	else {
		cout << "произвольный";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int a1, a2, b1, b2, c1, c2, d1, d2;

double AB, BC, CD, DA, AC, BD, A, B, C, D;

cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;

AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени

BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));

CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));

DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));

AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени

BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));

if(AB==CD && BC==DA) {

if (AB==BC){

if(AC==BD){

cout << "квадрат";

}

else {

cout << "ромб";

}

else

if (AC==BD){

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

}

else{

cout << "параллелограмм";

}

else

if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){

cout << "трапеция";

}

else {

cout << "произвольный";

}

return 0;

}

Решение

Для начала стоит найти длины всех сторон:

[latex]AB^{2}=((a1-b1)^{2}+(a2-b2)^{2})[/latex]. (аналогично для остальных сторон)

Затем можно найти длины диагоналей четырёхугольника

[latex]AC^{2}=((a1-c1)^{2}+(a2-c2)^{2})[/latex]. (аналогично для [latex]BD[/latex]).

Через условие задаем равность противоположных сторон [latex]AB=CD[/latex] и [latex]BC=DA[/latex]:

У ромба смежные стороны равны, но если у ромба диагонали равны, то это квадрат;
Если четырёхугольник не является квадратом, но диагонали равны, то это прямоугольник;
В противном случае — параллелограмм.

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

Код на ideone

Related Images:

e-olymp 60. Площадь многоугольника

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

Задача. Площадь многоугольника

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

Заданы координаты [latex]n[/latex] последовательных вершин многоугольника. Определить его площадь.

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

Первая строка содержит количество вершин многоугольника [latex]n[/latex]. В следующих [latex]n[/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex]x_i, y_i[/latex]. Известно, что [latex]3 \leq n \leq 1000, -1000 \leq x[i], y[i] \leq 1000[/latex].

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

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

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

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

№	Входные данные ([latex]n[/latex], [latex]x_i, y_i[/latex])	Выходные данные
1.	3, (0, 0), (0, 2), (2, 0)	2.000
2.	4, (-1000, 500), (-500, 1000), (2, 10), (35, 60)	339865.000
3.	10, (51, -20), (15, 3), (45, 200), (100, -100), (201, 55), (70, -80), (25, 333), (999, 0), (500, 77), (5, -6)	124562.500
4.	5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2)	1446.000

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main() { 
    int n, x1, x2, y1, y2, x, y; 
    double sum=0; 
    cin >> n >> x >> y; 
    x1=x; 
    y1=y; 
    for (int i=0; i<(n-1); i++) { 
        cin >> x2 >> y2; 
        sum=sum+(x1+x2)*(y2-y1); 
        x1=x2; 
        y1=y2; 
    } 
    sum=sum+(x+x2)*(y-y2); 
    cout << fixed << setprecision(3) << abs(sum) / 2 << endl;
    return 0; 
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

int n, x1, x2, y1, y2, x, y;

double sum=0;

cin >> n >> x >> y;

x1=x;

y1=y;

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

cin >> x2 >> y2;

sum=sum+(x1+x2)*(y2-y1);

x1=x2;

y1=y2;

}

sum=sum+(x+x2)*(y-y2);

cout << fixed << setprecision(3) << abs(sum) / 2 << endl;

return 0;

}

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

Даны координаты последовательных [latex]n[/latex] вершин многоугольника: [latex]x_i, y_i[/latex]. Для того, чтобы вычислить его площадь, воспользуемся формулой: [latex]S=\frac{1}{2}\cdot |\sum_{i=1}^{n}{(x_i + x_{i+1})\cdot (y_i — y_{i+1})}|[/latex], где [latex]x_0, y_0=x_{n+1}, y_{n+1}[/latex].

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

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

Ссылка на засчитанное решение на e-olymp.com.

Related Images:

Mif 17.15

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

Задача Mif17.15

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

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

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

В одной строке задано два числа – координаты точки latex[/latex].

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

Вывести: «Принадлежит» или «Не принадлежит»(без кавычек).

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

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

№	Входные данные	Выходные данные
1.	1.5 7	Не принадлежит
2.	3 4	Не принадлежит
3.	2 -3.6	Принадлежит
4.	5 0	Принадлежит
5.	0 1	Не принадлежит
6.	0 -4	Не принадлежит
7.	3 3	Принадлежит
8.	2 3	Принадлежит

Реализация

#include <iostream>
using namespace std;
 
int main () {
    double x, y, k, m, n;
    int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника
    cin >> x >> y; //координаты произвольной точки
    k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);
    m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);
    n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);
    cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main () {

double x, y, k, m, n;

int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника

cin >> x >> y; //координаты произвольной точки

k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);

m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);

n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);

cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");

return 0;

}

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

Пусть на плоскости дан треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]C(x_3, y_3)[/latex]. А [latex]D(x, y)[/latex] — произвольная точка на координатной плоскости. Положим, [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] — векторы.

Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
Если векторы заданы своими координатами [latex]a(x_1, y_1), b(x_2, y_2)[/latex], то их косое произведение [latex][a,b]=x_1\cdot y_2 — x_2\cdot y_1[/latex]. Пользуясь данной формулой, запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]D(x, y)[/latex]: [latex]k=x_1y_2 — x_2y_1 — x_1y + xy_1 + x_2y — xy_2=(x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex].
Далее запишем косое произведение векторов [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex]: [latex]m=x_2y_3 — x_3y_2 — x_2y + xy_2 + x_3y — xy_3=(x_2 -x)\cdot (y_ 3- y_2) — (x_3 — x_2)\cdot (y_2 — y)[/latex].
Запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] : [latex]n=x_1y_3 — x_3y_1 — x_1y + xy_1 + x_3y — xy_3=(x_3 — x)\cdot (y_1 — y_3) — (x_1 — x_3)\cdot (y_3 — y)[/latex].
Если [latex]k \leq 0 [/latex] и [latex]m \leq 0[/latex] и [latex]n \leq 0[/latex] или [latex]k \geq 0[/latex] и [latex]m \geq 0[/latex] и [latex]n \geq 0[/latex], то делаем вывод: точка принадлежит треугольнику.
Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

Ознакомиться с теоретическим материалом можно здесь.

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

Related Images:

Mif 17.16

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

Условие

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

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

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

№	Входные данные	Выходные данные
1	0 0	Yes
2	-6 0	Yes
3	5.0 -2.0	Yes
4	-3.33 -5	No
5	0.12345 0.54321	No

Код

#include <iostream>
using namespace std;

int main() {
    double x, y;	// Координаты точки
    cin >> x >> y;
    cout << ((x*x+y*y<=36&&(x<=0||y<=0))?"Yes":"No");	// Тернарная операция для определения принадлежности точки
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y; // Координаты точки

cin >> x >> y;

cout << ((x*x+y*y<=36&&(x<=0||y<=0))?"Yes":"No"); // Тернарная операция для определения принадлежности точки

return 0;

}

Решение

В основе заданной фигуры лежит круг с радиусом [latex]6[/latex] и центром в начале системы координат [latex](0, 0)[/latex], из которого исключена первая четверть. Таким образом, нам нужно удостовериться, что положение заданной точки одновременно удовлетворяет следующим условиям:

точка расположена в пределах круга, то есть сумма квадратов координат [latex]x^2+y^2[/latex] меньше или равна квадрату радиуса [latex]6^2=36[/latex];
хотя бы одна из координат точки [latex](x, y)[/latex] не превышает значения [latex]0[/latex] (другими словами, точка не лежит в первой четверти).

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

cout << ((x*x+y*y<=36&&(x<=0||y<=0))?"Yes":"No");

1	cout << ((xx+yy<=36&&(x<=0\|\|y<=0))?"Yes":"No");

Ссылки

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

Уравнение окружности;

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

Related Images:

Mif 17.18

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

Условие:

Принадлежит ли точка ([latex]x[/latex];[latex]y[/latex]) фигуре на рисунке? Вариант 18.

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

Два числа — координаты точки.

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

Слово «Yes», если точка принадлежит фигуре, в противном случае -«No».

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Result
6	0	Yes
0	0	Yes
5	2	No
-6	1	No

#include <iostream>
using namespace std;

int main() {
	double x,y;
	cin>>x>>y;
	if ((x>=0 && y>=0 && (x+y)<=6)||(x<=0 && y<=0 && (x+y)>=-6))
	cout<<"Yes"<<endl;
	else 
	cout<<"No"<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin>>x>>y;

if ((x>=0 && y>=0 && (x+y)<=6)||(x<=0 && y<=0 && (x+y)>=-6))

cout<<"Yes"<<endl;

else

cout<<"No"<<endl;

return 0;

}

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

Точка будет принадлежит фигуре тогда и только тогда, когда будут выполняться группы условий: или оба числа не отрицательные и их сумма не превышает 6, или оба числа не положительные, и их сумма не меньше 6. если одно из этих условий выполняется, то выводим «Yes», а иначе — «No».

Здесь решенная задача на сайте ideone.com.

Related Images:

Mif 17.5

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

Условие

Принадлежит ли точка [latex] \left( x,y \right) [/latex] фигуре на рисунке?

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

Координаты точки [latex]\left(x,y\right)[/latex] на плоскости.

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

Если точка принадлежит фигуре, вывести «Принадлежит» (без кавычек), в противном случае — «Не принадлежит».

Задача взята отсюда.

Тесты

№	x	y	Вывод
1	1	-1	Принадлежит
2	0	0	Принадлежит
3	0	4	Принадлежит
4	5	0	Принадлежит
5	0	4.00001	Не принадлежит
6	-3	5	Не принадлежит
7	2	3	Принадлежит

Решение

Фигура в задаче представлена в виде двух четвертей окружностей, лежащих в I и IV четвертях с радиусами [latex] R1 [/latex] и [latex] R2 [/latex] , которые равны соответственно [latex] 4 [/latex] и [latex] 5 [/latex]. Центры окружностей находятся в начале координатных осей. Сразу после ввода координат точки выполняем проверку принадлежности фигуре, а именно: координата [latex]X\ge0[/latex] ? В случае отрицательного ответа программа выведет сообщение «Не принадлежит». Одновременно со знаком [latex]X[/latex] выполняется проверка с помощью формулы, полученной из уравнения окружности: [latex]{\left(x-{X}_{c}\right)}^{2}+{\left(y-{Y}_{c}\right)}^{2}\le{R}^{2}[/latex], где [latex]X_{c}[/latex] и [latex]Y_{c}[/latex] — координаты центра окружности. Если координаты точки проходят данную проверку для соответствующего радиуса, который зависит от знака [latex]Y[/latex], то точка принадлежит фигуре, в противном случае выведется сообщение «Не принадлежит».

Код

#include <iostream>
using namespace std;

int main(){
	double y,Yc,x,Xc,R1,R2;
	Xc = 0; // координаты центров окружностей
	Yc = 0;
	R1 = 4; 
	R2 = 5;
	cin >> x >> y; 
	cout << ((x >= 0 && ((y > 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R1*R1) ||
			            (y <= 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R2*R2)))? "Принадлежит" : "Не принадлежит");
	return 0;
}

#include <iostream>

using namespace std;

int main(){

double y,Yc,x,Xc,R1,R2;

Xc = 0; // координаты центров окружностей

Yc = 0;

R1 = 4;

R2 = 5;

cin >> x >> y;

cout << ((x >= 0 && ((y > 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R1*R1) ||

(y <= 0 && ((y - Yc)*(y - Yc) + (x - Xc)*(x - Xc)) <= R2*R2)))? "Принадлежит" : "Не принадлежит");

return 0;

}

Код на сайте ideone.com находится здесь.

Related Images:

Ю2.6

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

Условие

Четырёхугольник [latex]ABCD[/latex] задан координатами своих вершин на плоскости: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex] и [latex]C(x_c,y_c)[/latex], [latex]D(x_d,y_d)[/latex]. Определить тип четырёхугольника: прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Учесть погрешность вычислений.

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

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

В одной строке заданы 8 чисел [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] — координаты вершин четырёхугольника [latex]ABCD[/latex], значения которых не превышают по модулю [latex]50[/latex].

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

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

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

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

№	Координаты [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex]	Вердикт (тип четырёхугольника)
1.	-5 -4 -1 -2 -4 3 -1 -8	Параллелограмм
2.	-2 -3 7 3 -2 1 7 1	Трапеция
3.	0 0 1 1 0 1 1 0	Прямоугольник
4.	50 -20 3 -50 7 6 2 3	Произвольный четырёхугольник
5.	2 -3 -6 -1 4 7 6 3	Параллелограмм
6.	1 -5 6 20 2 0 13 -9	Произвольный четырёхугольник
7.	0 1 2 1 0 1 1 0	Параллелограмм
8.	-6 0 6 0 1 5 -4 -8	Прямоугольник

Реализация

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

#include <iostream>

#include <cmath>

using namespace std;

int main () {

setlocale(LC_ALL,"Russian");

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

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

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

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

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

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

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

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

if (l==m)

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

else {

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

}

else {

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

}

else {

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

}

return 0;

}

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

Задан четырёхугольник [latex]ABCD[/latex] с такими координатами вершин: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex], [latex]C(x_c,y_c)[/latex] и [latex]D(x_d,y_d)[/latex]. В данной задаче будет уместным использование аппарата векторной алгебры. Пусть стороны четырёхугольника — векторы.
Очевидно, что для того, чтобы определить тип данного четырёхугольника, необходимо воспользоваться известными свойствами, а именно: свойствами прямоугольника, параллелограмма и трапеции. Так как в задаче используется аппарат векторной алгебры, обращаемся к таким свойствам векторов, как коллинеарность и равенство.
Сразу же установим: является ли четырёхугольник трапецией. Проверим одну из двух пар сторон на параллельность. Для этого воспользуемся условием коллинеарности векторов на плоскости: [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}[/latex], если [latex]a_i, b_i\ne0[/latex]. Координаты векторов [latex]\vec{b}[/latex] и [latex]\vec{d}[/latex] должны быть пропорциональны, что означает, что соответствующие стороны параллельны. Следовательно, [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Или же координаты векторов [latex]\vec{a}[/latex] и [latex]\vec{c}[/latex] должны быть пропорциональны. Проверяем: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex]. Если условие не выполняется, четырёхугольник произвольный. Если, напротив, координаты хотя бы одной пары векторов пропорциональны, четырёхугольник является трапецией.
Если четырёхугольник — параллелограмм, то обе пары его противоположных сторон параллельны. Проверим, выполняется ли: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex] и [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Если условие выполняется, то заданный четырёхугольник — параллелограмм.
Частным случаем параллелограмма является прямоугольник. Диагонали [latex] AC, BD[/latex] обозначим как [latex] l, m[/latex] соответственно. Пусть [latex] l, m[/latex] — векторы. Вычислим длины векторов [latex]\vec{l}[/latex], [latex]\vec{m}[/latex], пользуясь формулой. Получаем: [latex]\vec{|l|}= \sqrt{(x_c — x_a)\cdot (x_c -x_a) + (y_c — y_a)\cdot (y_c -y_a)}[/latex], [latex]\vec{|m|}= \sqrt{(x_d — x_b)\cdot (x_d -x_b) + (y_d — y_b)\cdot (y_d -y_b)}[/latex]. При условии, что [latex]\vec{l}=\vec{m}[/latex], имеем прямоугольник.

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

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

Related Images:

ML18

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

Задача ML18

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

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

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

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex], значения которых не превышают по модулю [latex]100[/latex].

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

Вывести периметр [latex]p[/latex] данного треугольника.

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

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

№	Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex])	Выходные данные
1	2 2 5 1 0 -1 3 5 10	16.0261556346
2	1 4 5 3 6 0 10.5 -2 -1	31.9047289894
3	15 26 13 32 18 56 80 0 -6.2	212.0962807371
4	-13 68 44 99 -100 70 0 2 1	450.5748518262
5	100 9 17 18 29 88 65 -16 0.36	310.4318979186

Реализация

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

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main ()

{

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

long double a, b, c, p;

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

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

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

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

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

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

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

p= a + b + c;

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

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

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

return 0;

}

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

Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

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

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