Перейти к содержимому


LVP

Регистрация: 21 Dec 2011
Offline Активность: Вчера, 08:37 PM
*****

Мои темы

Выпуклая оболочка Грехэма (сортировка по косому произведению)

24 October 2020 - 11:57

Код от Кузьмичева Алексея, нахождения выпуклой оболочки по Алгоритму Грехема , используя сортировку точек по Углу через косое произведение векторов (решение задачи Informatics/mccme.ru 1877)

#include <bits/stdc++.h>
 
using namespace std;
 
struct point /// структура обозначающая точку в нашей системе координат
{
	int x, y;
};
 
point fst; /// 1 - я точка
 
long long dist_sq(int x1 , int y1 , int x2 , int y2) { /// функция, которая возвращает квадрат расстояние от 1-й точки до другой
	long long X1 = x1 , X2 = x2 , Y1 = y1 , Y2 = y2;
	return ((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2));
}
 
long long cross (point a1, point a2, point b1, point b2) /// функция, которая возвращает косое произведение векторов
{
return 1ll * (a2.x - a1.x) * (b2.y - b1.y) - 1ll * (b2.x - b1.x) * (a2.y - a1.y);
}
 
bool comporator(point l , point r) { /// компоратор для сравнения значений косого произведения в sort
	if (cross(l , fst , fst , r) < 0) {
    	return 1;
	}
	if (cross(l , fst , fst , r) == 0 && dist_sq(fst.x , fst.y , l.x , l.y) < dist_sq(fst.x , fst.y , r.x , r.y)) {
    	return 1;
	}
	return 0;
}
 
int main() {
	int n;
	cin >> n;
	point a[n];
	for (int i = 0; i < n; i++) { /// считывание + нахождение самой левой точки из самых нижних
    	cin >> a[i].x >> a[i].y;
    	if (a[0].y > a[i].y) {
        	swap(a[0] , a[i]);
    	} else {
        	if (a[0].y == a[i].y && a[i].x < a[0].x) {
            	swap(a[0] , a[i]);
        	}
    	}
	}
	fst = a[0]; /// самая первая точка
	sort(a + 1 , a + n , comporator); /// сортировка(от второй точки)
	deque <point> st; /// стек для построения оболочки
	st.push_back(a[0]);
for (int i = 1; i < n; i++) /// проход по алгоритму построения
{
  while (st.size() > 1 && cross(st[st.size() - 2] , st[st.size() - 1] , st[st.size() - 1] , a[i]) <= 0)
  {
        	st.pop_back();
  }
        	if (st.back().x != a[i].x || st.back().y != a[i].y) st.push_back(a[i]);
  }
 
	if (n % 2 != 0) { /// т.к. в 1877 если n нечетно нужно вывести оболочку по часовой стрелке, то развернём стек
    	reverse(st.begin() , st.end());
	}
 
	cout << st.size() << endl;
	for (auto to : st) { /// вывод оболочки
    	cout << to.x << " " << to.y << endl;
	}
	return 0;
}

Выпуклая оболочка Грэхема-Эндрю

14 October 2020 - 11:00

Выпуклая оболочка Грэхема-Эндрю (от Рубиша Артура)

Одной из наиболее известных задач на геометрию - задача на построение выпуклой оболочки(ссылка на задачу внизу). Кто-то делает его алгоритмом Джарвиса за квадрат, кто-то - обычным алгоритмом Грэхема за n log n, но с использованием вещественных чисел.

Однако всё же есть несколько способов обойтись без ошибки по времени и вещественных чисел. Одним из них является алгоритм Грэхема-Эндрю. Алгоритм является оптимальным и использует только сложение, умножение и вычитание.

Суть алгоритма довольно несложная, если вы хорошо понимаете алгоритм Грэхема. Давайте найдём самую левую нижнюю и самую правую верхнюю точки из данных нам. Пусть это будут точки А и В соответственно. Дальше мы проведём прямую через эти точки. Так, мы разделили прямую на две части - верхнюю и нижнюю(Точки на этой прямой, кроме А и В, мы не учитываем ни в какую из частей. Сами же точки А и В войдут в обе части).Дальше мы сортируем все точки по абсциссе, а при их равенстве - по ординате. Всё, что нам осталось сделать - использовать алгоритм Грэхема для построения сначала верхней, а затем и нижней части оболочки.

Код(для задачи, указанной ниже).

#include <bits/stdc++.h>
#define ld long double
#define int long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
using namespace std;
int32_t main ()
{
    ///Алгоритм Грэхема-Эндрю, написан и объяснён _GreatArthur_
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    int copy = n;
    long double x[n], y[n];
    ///Используем map для удаления одинаковых точек.
    map < pair < ld, ld >, int > mp;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        mp[{x[i], y[i]}]++;
        if (mp[{x[i], y[i]}] > 1)
        {
            i--;
            n--;
        }
    }
    ///Отдельно проверяем частный случай.
    if (n == 1)
    {
        cout << 1 << endl << x[0] << ' ' << y[0];
        return 0;
    }
    ///Находим номера точек А и В.
    int numA = 0, numB = 0;
    for (int i = 0; i < n; i++)
    {
        if (x[numA] > x[i] || (x[numA] == x[i] && y[numA] > y[i]))
        numA = i;
        if (x[numB] < x[i] || (x[numB] == x[i] && y[numB] < y[i]))
        numB = i;
    }
    ///Создаём два множества для верхней и нижней части оболочки.
    vector < int > up, down;
    up.pb(numA);
    down.pb(numA);
    ///Сортируем точки по абсциссе(v[i].F), а при их равенстве - по ординате(v[i].S.F). Чтобы понять номер точек после сортировки, также храним их номер(v[i].S.S).
    vector < pair < int, pair < int, int > > > v;
    for (int i = 0; i < n; i++)
        v.pb({x[i], {y[i], i}});
    sort(v.begin(), v.end());
    int ii = 0;
    ///Ищем верхнюю часть оболочки.
    do
    {
        ii++;
        if ((x[v[ii].S.S] - x[numA]) * (y[numB] - y[numA]) - (y[v[ii].S.S] - y[numA]) * (x[numB] - x[numA]) <= 0 && v[ii].S.S != numB) continue;
        ///Для каждой точки мы проверяем, сверху ли она или её номер - numB.Если да, то мы делаем алгоритм ниже, иначе - просто игнорируем её.
        while (up.size() > 1 && (x[v[ii].S.S] - x[up[up.size() - 2]]) * (y[up[up.size() - 1]] - y[up[up.size() - 2]]) - (y[v[ii].S.S] - y[up[up.size() - 2]]) * (x[up[up.size() - 1]] - x[up[up.size() - 2]]) >= 0)
            up.pop_back();
        up.pb(v[ii].S.S);
    }
    while (ii < v.size() - 1);
    ii = 0;
    ///Ищем нижнюю часть оболочки.
    do
    {
        ii++;
        if ((x[v[ii].S.S] - x[numA]) * (y[numB] - y[numA]) - (y[v[ii].S.S] - y[numA]) * (x[numB] - x[numA]) >= 0 && v[ii].S.S != numB) continue;
        ///Для каждой точки мы проверяем, снизу ли она или её номер - numB.Если да, то мы делаем алгоритм ниже, иначе - просто игнорируем её.
        while (down.size() > 1 && (x[v[ii].S.S] - x[down[down.size() - 2]]) * (y[down[down.size() - 1]] - y[down[down.size() - 2]]) - (y[v[ii].S.S] - y[down[down.size() - 2]]) * (x[down[down.size() - 1]] - x[down[down.size() - 2]]) <= 0)
            down.pop_back();
        down.pb(v[ii].S.S);
    }
    while (ii < v.size() - 1);
    ///Выводим оболочку.
    cout << up.size() + down.size() - 2 << endl;
    if (copy % 2 == 0)
    {
        for (int i = 0; i < up.size(); i++)
            cout << x[up[i]] << ' ' << y[up[i]] << endl;
        for (int i = down.size() - 2; i >= 1; i--)
            cout << x[down[i]] << ' ' << y[down[i]] << endl;
    }
    else
    {
        for (int i = 1;i <= down.size() - 2; i++)
            cout << x[down[i]] << ' ' << y[down[i]] << endl;
        for (int i = up.size() - 1;i >= 0;i--)
            cout << x[up[i]] << ' ' << y[up[i]] << endl;
    }
    return 0;
}


Сдать задачу:

https://informatics....hapterid=1877#1

Расписание август-октябрь 2020

10 August 2020 - 05:56

Сборы к IOI и к Юнионскому Межнару будут проходить на Яндекс-контесте 12.08-14.08)
Ссылка на контест: https://official.con....ru/beloi-sel20
10.08.20 - сборов не будет.
11.08.20 - сборов нет. Ждем восстановления интернета.
Читайте теорию , повторяйте алгоритмы!!!
всем участникам сборов нужно установить программу Discord , войти под своей Фамилией и следить за сообщениями жюри: Адрес сервера для общения в Discord: https://discord.gg/N9wsgad
12.08. - с 12.00 старт соревнования
13.08 - с 12.00 старт соревнования

Внимание! с 18 по 31 августа
СБОРЫ для отбора на Межнары: IOI и Юниорский! Начинаются контесты ровно в 9:00. Но для тех, кто не отбирается на eJOI и IOI можно будет стартовать после 14:00

Внимание! Завтра (а также ср, чт и пт) отбор на eJOI (Межнар для Юниоров) . Для тех,у кого в логине есть eJOI старт будет выставлен на 9:00, остальные могут стартовать с 14:00 до 15:00.

Внимание!!! Начинаем подготовку к командному чемпионату БГУ и ВГУ!
вт 25.08.2020 - в гимназии 8 тренировочная командная олимпиада 9.00-14.00 https://codeforces.c...99/virtual/true Несем свои ноутбуки (у кого есть).
Пробный состав командных олимпиад следующий:
Смирнов+Тилигузов+Гнедько
Адаменко+Новицкий+Патрушева
Яцук+Грунтов+Балюконис
Заровский+Борчук+Бовбель
Соколовская+Пронина+Ильина
Ришко+Дюбкова+Зимницкий
Луценко+Андреева+Рубиш
ср 26.08.2020 - в гимназии 8 тренировочная командная олимпиада 9.00-14.00 https://codeforces.c.../101614/virtual Разбор: http://neerc.ifmo.ru...11-advanced.pdf

чт 27.08.2020 - в гимназии 8 тренировочная командная олимпиада 9.00-14.00 https://codeforces.c.../101551/virtual Разбор: https://neerc.ifmo.r...al-20170930.pdf

пт 28.08.2020 - в гимназии 8 тренировочная командная олимпиада 9.00-13.00 https://codeforces.c...61/virtual/true

29.08. 20 - дома 14.00-18.00 тренировочная личная олимпиада по логинам-паролям КЮПа
https://official.con...ex.ru/CYF/news/
30.08.20 - дома 13.00-17.00 тренировочная личная олимпиада по логинам-паролям КЮПа + 17.35 codeforces

сб 05.09.2020 - тренировочная командная олимпиада Гимназия 8 каб 325 09.00-14.00
Для сильных команд: https://codeforces.c.../101294/virtual
Для слабых команд:
https://codeforces.c...93/virtual/true
+ дома 14.00-18.00 тренировочная личная олимпиада по логинам-паролям КЮПа

вс 06.09.2020 - дома 13.00-17.00 тренировочная личная олимпиада по логинам-паролям КЮПа + 17.35 codeforces

сб 12.09.2020 - тренировочная командная олимпиада Гимназия 8 каб 325 09.00-14.00
Для сильных команд: https://codeforces.c.../101297/virtual
Для слабых команд: https://codeforces.c.../101296/virtual
+ дома 12.00-16.00 тренировочная личная олимпиада по логинам-паролям КЮПа https://official.con...ex.ru/CYF/news/ или 16.35-18.35 Codeforces

вс 13.09.2020 - дома 14.00-18.00 тренировочная личная олимпиада по логинам-паролям КЮПа https://official.con...ex.ru/CYF/news/

пн 14.09.2020 - дома 17.35-19.35 Codeforces

сб 19.09.2020 - 12.00-16.00 личная областная Гомельская олимпиада по логинам-паролям КЮПа https://official.con...ex.ru/CYF/news/

вс 20.09.2020 - дома 14.00-18.00 тренировочная личная олимпиада по логинам-паролям КЮПа https://official.con...ex.ru/CYF/news/

сб 26.09.2020 - в гимназии 8 тренировочная командная олимпиада Гимназия 8 каб 325 11.00-16.00
https://codeforces.c...29/virtual/true
Разбор: http://neerc.ifmo.ru...14-analysis.pdf
Зарегистрируйте команды на Чемпионат БГУ (первое слово в названии команды делайте Витебск: ) https://forms.gle/xZdJEvAGjsinhY3SA

вс 27.09.2020 - в гимназии 8 тренировочная командная олимпиада Гимназия 8 каб 325 11.00-16.00 (Заранее подайте заявку от команды на сайте acmp.ru, первое слово в названии команды делайте Витебск:) +дополнительно: https://codeforces.c...19/virtual/true + Codeforces дома 18.05-20.05

Зарегистрируйтесь на Иннополис:
https://dovuz.innopo...tm_medium=25_09

пн 28.09.20 - зарегистрируйтесь на "Высшую пробу" https://olymp.hse.ru/mmo/instr-reg

сб 03.10.20 - в Гимназии 8 9.50-15.00 командный чемпионат БГУ
вс 04.10.20 - в Гимназии 8 командная олимпиада https://codeforces.c...94/virtual/true 11.00-16.00

сб 10.10.20 - в Гимназии 8 тренировочная командная олимпиада 11.00-16.00 https://codeforces.c.../101136/virtual разбор: http://neerc.ifmo.ru...al-20161023.pdf + Зарегистрируйтесь на Технокубок https://technocup.mail.ru/register/ + зарегистрируйтесь на Всесибирскую олимпиаду (на личную ) через личный кабинет https://vsesib.nsu.ru/personal/ и в тестирующей системе https://olympic.nsu....s-new/login.cgi
вс 11.10.20 - в Гимназии 8 командная олимпиада Opencup.ru 11.00-16.00

чт 15.10.20 - зарегистрируйтесь на личную олимпиаду МГУ (дает поступление) https://olymp.msu.ru...vatsya-na-sajte и на Надежду энергетики http://www.energy-ho.../reg_user.html? и зарегистрируйтесь на "Высшую пробу" https://olymp.hse.ru/mmo/instr-reg + зарегайтесь на олимпиаду СПбГУ https://olympiada.sp...u/instrukcziya/ (самостоятельно в дальнейшем отслеживайте даты проведения отборов и финалов)
сб 17.10.20 - 11.00-16.00 в Гимназии 8 тренировочная командная олимпиада https://codeforces.c.../100538/virtual + дома 17.00-21.00 личная Хорвадская олимпиада на сайте https://hsin.hr/coci/
вс 18.10.20 - 9.00-14.00 дома Всесибирская олимпиада https://olympic.nsu.ru/nsuts-new/login (заранее зарегистрируйтесь!!!) Разбор олимпиады: https://olympic.nsu....or_inet2020.pdf

cб 24.10.20 - 11.00-16.00 в Гимназии 8 тренировочная командная олимпиада https://codeforces.c.../102772/virtual (сильным командам надо решить все задачи!!!)
Разбор: http://neerc.ifmo.ru...al-20201018.pdf

вс 25.10.20 - 16.30-21.30 в Гимназии 8 командная Питерская олимпиада http://neerc.ifmo.ru...l/io/index.html (команды 01, 02, 03 претендующие на Всероссийскую олимпиаду, решают усложненный уровень (спросите разрешение у родителей) , остальные команды по желанию решают базовый уровень до 19.30 или усложненный до 21.30.
Все дома 14.00 решают отбор на Технокубок https://technocup.ma...als/raspisanie/ )

Внимание!!! Болгария пригласила поучаствовать в международной олимпиаде, которая состоится on-line 19.11-22.11. Заявку на участников надо подать до 11.11. Нужно отобрать 4 человека в основную команду для старшей лиги и 4 человека для младшей лиги (дата рождения не старше 31.12.2004). Можно в дополнительных командах участвовать (отбирают по 20 человек в каждую лигу). Прошу всех ознакомиться с задачами Болгарской олимпиады прошлого года: http://iati-shu.org/en/home/

чт 29.10.20 - в гимназии 8 командный чемпионат ВГУ 13.00-16.00

АДРЕС КОНТЕСТА

https://official.contest.yandex.ru/contest/21618/enter



(тур всего 3 часа, берите конспекты, задачи бывают "свеченными" и с геометрией, тесты бывают пустыми строками и крайними случаями из условия)

Зарегистрируйтесь на МИССИС!!! https://forms.gle/wDbWNUUE8p6tfkSVA

сб 31.10.20 - 12.00-16.00 в Гимназии 8 официальный республиканский отбор на Болгарскую олимпиаду на Яндекс-контесте https://official.con...olving-20200829 (логины и пароли КЮПа). Берут из таблицы по 24 участника в каждую из групп: старшую (до конца 2004 года рождения) и младшую (с 2005 года рождения). Но в 2-е основные команды от страны попадают только 8 участников (по 4 в обе группы) . Писать отбор надо в гимназии и фото участников отправляется жюри.

Занятия на осенних каникулах:

Задача про Коня

23 April 2020 - 20:45

Автор темы: Рубиш Артур и Козлова Настя (7 класс)

Задача: Шахматный конь стоит на доске 8х8 в клетке х1, у1. Также на доске стоят K других фигур: на клетке a[i],b[i] стоит i-я фигура. Коню нужно добраться до клетки х2,у2 за наименьшее количество ходов.

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

1) Решение задачи стеком:

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first
#define endl '\n'
#define pii pair < int, int >
using namespace std;

const int N = 3e5 + 10;
const int inf = 2e10;
const int smi[8] = {-2,-2,-1,-1,1,1,2,2}, smj[8] = {1,-1,2,-2,2,-2,-1,1};
int used[10][10], xx, yy;

void SOS(int x, int y)
{
//2.1.Функция SOS.
for (int i = 0;i < 8;i++)
{
xx = x + smi[i];
yy = y + smj[i];
//хх и уу – место, куда конь может встать.
if (xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && used[xx][yy] == 0)
return;
//Если хх и уу не вылазят за доску и конь там ещё не был, ставим его туда.Иначе присваиваем в хх и уу -1.
}
xx = -1;
yy = -1;
}

int main()
{
for (int i = 0;i < 10;i++)
for (int j = 0;j < 10;j++)
used[i][j] = 0;
//1.Ввод.
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--;y1--;x2--;y2--;
int n;
cin >> n;
int a[n], b[n];
for (int i = 0;i < n;i++)
{
cin >> a[i] >> b[i];
a[i]--; b[i]--;
used[a[i]][b[i]] = 1; //Помечаем i-го коня.
}
stack < pii > st;
used[x1][y1] = 1;
st.push({x1, y1});
//2,Основной код.
while (!st.empty() && !used[x2][y2])
{
int x = st.top().F, y = st.top().S; // х и у – место, где стоит конь сейчас.
SOS(x, y); //Функция находится в начале кода.
if (xx != -1)
{
st.push({xx, yy});
used[xx][yy] = 1;
//Если мы нашли хх и уу, ставим коня туда и помечаем место, где мы теперь стоим.
}
else st.pop();
}
//3.Вывод.Если клетка с номером х2.у2 помечена, выводим путь.
if (used[x2][y2] == 1)
{
cout << "Yes" << endl;
vector < pii > ans;
while (!st.empty())
{
ans.pb({st.top().F, st.top().S});
st.pop();
}
reverse(ans.begin(), ans.end());
for (auto to:ans)
cout << to.F + 1 << ' ' << to.S + 1 << endl;
}
else cout << "No";
}

2) Также можно решить эту задачу вектором:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first
#define endl '\n'
#define pii pair < int, int
using namespace std;
const int N = 3e5 + 10;
const int inf = 2e10;
const int smi[8] = {-2,-2,-1,-1,1,1,2,2}, smj[8] = {1,-1,2,-2,2,-2,-1,1};
int used[10][10], xx, yy;
void SOS(int x, int y)
{
//2.1.Функция SOS.
for (int i = 0;i < 8;i++)
{
xx = x + smi[i];
yy = y + smj[i];
if (xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && used[xx][yy] == 0)
return;
}
//Если хх и уу не вылазят за доску и конь там ещё не был, ставим его туда.Иначе присваиваем в хх и уу -1.
xx = -1;
yy = -1;
}

int main()
{
for (int i = 0;i < 10;i++)
for (int j = 0;j < 10;j++)
used[i][j] = 0;
//1.Ввод.
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--;y1--;x2--;y2--;
int n;
cin >> n;
int a[n], b[n];
for (int i = 0;i < n;i++)
{
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
used[a[i]][b[i]] = 1; //Помечаем i-го коня.
}
vector < pii > st;
used[x1][y1] = 1;
st.push_back({x1, y1});
//2.Основной код.
while (!st.empty() && !used[x2][y2])
{
int x = st.back().F, y = st.back().S; // х и у – место, где стоит конь сейчас.
SOS(x, y); //Функция находится в начале кода.
if (xx != -1)
{
st.push_back({xx, yy});
used[xx][yy] = 1;
//Если мы нашли хх и уу, ставим коня туда и помечаем место, где мы теперь стоим.
}
else st.pop_back();
}
//3.Вывод.Если клетка с номером х2.у2 помечена, выводим путь.
if (used[x2][y2] == 1)
{
cout << "Yes" << endl;
for (auto to:st)
cout << to.F + 1 << ' ' << to.S + 1 << endl;
}
else cout << "No";
}

3) решение задачи рекурсией:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define S second
#define F first
#define endl '\n'
#define pii pair < int, int >

using namespace std;
const int N = 3e5 + 10;
const int inf = 2e10;
const int smi[8] = {-2,-2,-1,-1,1,1,2,2}, smj[8] = {1,-1,2,-2,2,-2,-1,1};
int used[10][10], xx, yy, x1, y1, x2, y2;
stack < pii > st;

void SOS(int x, int y)
{
if (used[x2][y2] == 1)
return;
//Если финишная клетка уже помечена, останавливаем рекурсию.
for (int i = 0;i < 8;i++)
{
xx = x + smi[i];
yy = y + smj[i];
if (xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && used[xx][yy] == 0 && used[x2][y2] == 0)
{
st.push({xx, yy});
used[xx][yy] = 1;
SOS(xx, yy);
//Если мы нашли хх и уу, ставим коня туда,помечаем место, где мы теперь стоим и заново запускаем рекурсию.
}
}
if (used[x2][y2] == 0) st.pop();
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 0;i < 10;i++)
for (int j = 0;j < 10;j++)
used[i][j] = 0;
//1.Ввод.
cin >> x1 >> y1 >> x2 >> y2;
x1--;y1--;x2--;y2--;
int n;
cin >> n;
int a[n], b[n];
for (int i = 0;i < n;i++)
{
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
used[a[i]][b[i]] = 1;//Помечаем i-го коня.
}
used[x1][y1] = 1;
st.push({x1, y1});
SOS(x1, y1);//Функция находится в начале кода.
//3.Вывод.Если клетка с номером х2.у2 помечена, выводим путь.
if (used[x2][y2] == 1)
{
cout << "Yes" << endl;
vector < pii > ans;
while (!st.empty())
{
ans.pb({st.top().F, st.top().S});
st.pop();
}
reverse(ans.begin(), ans.end());
for (auto to:ans)
cout << to.F + 1 << ' ' << to.S + 1 << endl;
}
else cout << "No";
}

4) решение задачи очередью от
Анастасии Козловой (7 класс)
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
int q[2][100000],a[110][110], uk,un,i,j;
void sos(int x, int y)
{
if (a[x][y]==0)
{
a[x][y]=a[i][j]+1;
q[0][uk]=x;
q[1][uk]=y;
uk++;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n,m,x1,x2,y1,y2;
char z[110][110];
cin»n;
//int m;
cin»m;
for(int t=2; t<=n+1; t++)
for(int h=2; h<=m+1; h++)
{
cin»z[t][h];
if (z[t][h]=='X')
a[t][h]=-1;
else
a[t][h]=0;
if (z[t][h]=='S')
{
x1=t;
y1=h;
}
if (z[t][h]=='F')
{
x2=t;
y2=h;
}

}
for(int i=0; i<=n+3; i++)
{
a[i][0]=-1;
a[i][1]=-1;
a[i][m+2]=-1;
a[i][m+3]=1;
}
for(int i=0; i<=m+3; i++)
{
a[0][i]=-1;
a[1][i]=-1;
a[n+2][i]=-1;
a[n+3][i]=-1;
}
un=0;
uk=1;
q[0][0]=x1;
q[1][0]=y1;
a[x1][y1]=1;
while (uk>un && a[x2][y2]==0)
{
i=q[0][un];
j=q[1][un];
un++;
sos(i+1,j+2);
sos(i-1,j-2);
sos(i+2,j+1);
sos(i-2,j-1);
sos(i-1,j+2);
sos(i+1,j-2);
sos(i+2,j-1);
sos(i-2,j+1);
}
//cout«a[x2][y2]«' '«x2«' '«y2«' '«endl;
vector<pair<int, int> > ans;
if (a[x2][y2]!=0)
cout«"Yes" « endl;
else
{
cout«"No"«endl;
return 0;
}
int k=a[x2][y2];
for(int l=k; l>=2; l--)
{
ans.pb({x2-1,y2-1});
if (a[x2-1][y2-2]==l-1)
{
x2--;
y2-=2;
}
else
if (a[x2+1][y2+2]==l-1)
{
x2++;
y2+=2;
}
else
if (a[x2-1][y2+2]==l-1)
{
x2--;
y2+=2;
}
else
if (a[x2+1][y2-2]==l-1)
{
x2++;
y2-=2;
}
else
if (a[x2-2][y2-1]==l-1)
{
x2-=2;
y2--;
}
else
if (a[x2+2][y2+1]==l-1)
{
x2+=2;
y2++;
}
else
if (a[x2-2][y2+1]==l-1)
{
x2-=2;
y2++;
}
else
if (a[x2+2][y2-1]==l-1)
{
x2+=2;
y2--;
}
}
reverse(ans.begin(),ans.end());
for(int o = 0; o<ans.size(); o++)
cout«ans[o].F«' '«ans[o].S«endl;
return 0;
}

расписание февраль-май 2020 9-11 класс

29 January 2020 - 22:21

Расписание на февраль-июнь 2020 (следите за изменениями)

ДОРЕШКА отбора на ИОИП (прошел 26.01.2020): https://codeforces.com/gym/102498

сб 01.02.2020 - 9.00-14.00 в Гимназии 8 тренировочная олимпиада https://codeforces.c...80/virtual/true
Разбор внизу
вс 02.02.2020 - 12.00-16.00 в Гимназии 8 отбор в ЗКШ

СБОРЫ ПО ПОДГОТОВКЕ К РЕСПУБЛИКАНСКОЙ ОЛИМПИАДЕ
пн 03.02.2020 -9.00-17.00
вт 04.02.2020 - 8.30-17.00
ср 05.02.2020 - 8.30-17.00
чт 06.02.2020 -9.00-17.00
пт 07.02.2020 -9.00-17.00
сб 08.02.2020 -9.00-16.00 + дома 17.00-21.00 Хорватская олимпиада https://hsin.hr/coci/
вс 09.02.2020 -выходной

пн 10.02.2020 - в своих школах 11.30-16.30 тренировочная олимпиада по подготовке к Республиканской олимпиаде на сайте https://official.con...st/17086/enter/ (использовать логин-пароль КЮПа, полученные вами ранее).
Разбор 2-х дней: http://neerc.ifmo.ru...9-solutions.pdf
вт 11.02.2020 - в своих школах 11.00-16.00 тренировочная олимпиада по подготовке к Республиканской олимпиаде на сайте https://official.con...st/17086/enter/
ср 12.02.2020 - в своих школах 11.00-16.00 тренировочная олимпиада по подготовке к Республиканской олимпиаде на сайте https://official.con...st/17086/enter/
Разбор прикреплен внизу.
чт 13.02.2020 - в своих школах 11.00-16.00 тренировочная олимпиада по подготовке к Республиканской олимпиаде на сайте https://official.con...st/17086/enter/
Разбор: https://yadi.sk/d/AfPkeJ87WmbeNg
пт 14.02.2020 - в своих школах 11.00-16.00 тренировочная олимпиада по подготовке к Республиканской олимпиаде на сайте https://official.con...st/17086/enter/
Разбор: https://yadi.sk/d/ip2NKbMasgJYcA
сб 15.02.2020 - 10.00-15.00 в гимназии 8 тренировочная олимпиада КЮПа https://official.con...st/17086/enter/ + ДОМА отбор на ИОИП 16.00-21.00 на сайте http://neerc.ifmo.ru...l/io/index.html
вс 16.02.2020 -выходной

пн 17.02.2020 - пт 21.02.2020 - в своих школах во время погружения (на свободном посещении) решать срочно Московскую олимпиаду 1 уровня МОШ http://mos-inf.olimpiada.ru/news/74, Респы прошлых лет dl.gsu.by и делать дорешивания по разбору (скачать его с Беседы Программисты). Дорешать область 2020 https://ext.contest....st/16849/enter/
сб 22.02.2020 - в Гимназии 8 Американская олимпиада 09.00-14.00 на сайте http://usaco.org/
вс 23.02.2020 - поездка в Минск на Иннополис: встреча на вокзале под табло около ж/д моста в 6.15 (взять паспорт, справку со школы и Разрешение на обработку данных от родителей). Вагон 5, отъезд в 6.33. Из Минска выезд в 18.43

сб 29.02.2020 - в Гимназии 8 Личная олимпиада 09.00-12.00 на сайте https://codeforces.c.../100981/virtual
Разбор скачать внизу
вс 01.03.2020 в Гимназии 8 Технокубок 11.00-16.00 (те кто прошел в финал несут паспорт)

сб 07.0.2020 - в Гимназии 8 9.00-14.00 личная олимпиада ИОИП 2013 https://codeforces.c...100174/virtual (Разбор скачать внизу) + дома решать Хорватскую олимпиаду 17.00-21.00 https://hsin.hr/coci/
вс 08.03.2020 - отдых. Подготовка к сборам.

ср 11.03.2020 - 8.30-16.00 сборы по подготовке к Республиканской олимпиаде в кабинете 325 Гимназии 8
чт 12.03.2020 - 8.30-16.00 сборы по подготовке к Республиканской олимпиаде в кабинете 325 Гимназии 8
пт 13.03.2020 - 8.30-16.00 сборы по подготовке к Республиканской олимпиаде в кабинете 325 Гимназии 8
сб 14.03.2020 - 15.00-20.00 ДОМА личная олимпиада на сайте http://neerc.ifmo.ru...l/io/index.html. Разбор: http://neerc.ifmo.ru...-individual.pdf. ДОРЕШКА ОЛИМПИАДЫ: https://codeforces.com/gym/102551
пн 16.03.2020 - 8.30-16.00 дистанционные сборы по подготовке к Республиканской олимпиаде + регистрация команд на Чемпионат БГУИР http://acm.bsuir.by/...20/registration
вт 17.03.2020 - 8.30-16.00 дистанционные сборы по подготовке к Республиканской олимпиаде
ср 18.03.2020 - 8.30-16.00 дистанционные сборы по подготовке к Республиканской олимпиаде
чт 19.03.2020 - 8.30-16.00 дистанционные сборы по подготовке к Республиканской олимпиаде
пт 20.03.2020 - личная олимпиада на сайте https://codeforces.c.../101284/virtual Разбор: http://neerc.ifmo.ru...-individual.pdf
сб 21.03.2020 - 9.45-14.00 в гимназии 8 отбор на командный чемпионат БГУИР (решать можно до 6 апреля)
вс 22.03.2020 - дома личная олимпиада на сайте https://codeforces.c...27/virtual/true
Разбор прикреплен внизу.

Дистанционные СБОРЫ ПО ПОДГОТОВКЕ К РЕСПУБЛИКАНСКОЙ ОЛИМПИАДЕ (Мозырь проводит)
пн 23.03.2020 -11.30-16.30 на сайте https://official.con...st/17686/enter/ (использовать логин-пароль КЮПа, полученные вами ранее). После олимпиады скачивайте с сайта разбор и делайте дорешивание.
вт 24.03.2020 - 11.00-16.00
ср 25.03.2020 - 11.00-16.00
чт 26.03.2020 -11.00-16.00
пт 27.03.2020 -11.00-16.00
сб 28.03.2020 -11.00-16.00 (желательно решать дома. В Гимназию 8 решать приходят только абсолютно здоровые и нуждающиеся в обществе единомышленников Республиканцы)
вс 29.03.2020 - дома дорешка сборов и ЗКШ

ПРОДОЛЖАЕМ Дистанционные СБОРЫ ПО ПОДГОТОВКЕ К РЕСПУБЛИКАНСКОЙ ОЛИМПИАДЕ (олимпиада планируется в мае)
пн 30.03.2020 - дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17759/enter/ (использовать логин-пароль КЮПа, полученные вами ранее). После олимпиады скачивайте с сайта в папке Solutions материалы олимпиады (там будет PDF с разобранными авторскими решениями) и делайте дорешивание!!!.
Прошу всех серьезно отнестись и с пользой для ума и здоровья провести каникулы!!!
вт 31.03.2020 - дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17759/enter/ и делать дорешку
ср 01.04.2020 - дома делать дорешку сборов, ЗКШ , прошлых олимпиад, решать Респы прошлых лет.
чт 02.04.2020 -дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17759/enter/ и делать дорешку
пт 03.04.2020 -дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17759/enter/ и делать дорешку
сб 04.04.2020 - дома 15.00-20.00 решать олимпиаду на сайте http://neerc.ifmo.ru...l/io/index.html

пн 06.04.2020 - дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17885/enter/ (использовать логин-пароль КЮПа, полученные вами ранее). После олимпиады скачивайте с сайта в папке Solutions материалы олимпиады и делайте дорешивание!.
Прошу всех серьезно отнестись и с пользой для ума и здоровья провести еще одну неделю каникул.
вт 07.04.2020 - дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17759/enter/ и делать дорешку + 17.00-22.00 командный полуфинал БГУИР (команды обсуждают задачи общаясь звонками в месенджерах)
Итоги: https://official.con...7438/standings/
ср 08.04.2020 - дома делать дорешку сборов, ЗКШ , прошлых олимпиад, решать Респы прошлых лет.
чт 09.04.2020 - дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17885/enter/ и делать дорешку
пт 10.04.2020 - дома 12.00-17.00 решать олимпиаду на сайте https://official.con...st/17885/enter/ и делать дорешку
сб 11.04.2020 - дома делать дорешку сборов, ЗКШ , прошлых олимпиад, решать Респы прошлых лет, решать задачи с архива Codeforces.ru.
вс 12.04.2020 - дома 17.05-19.05 Codeforces.ru (заранее подайте заявку) + делать дорешку сборов, ЗКШ , прошлых олимпиад, решать Респы прошлых лет, решать задачи с архива Codeforces.ru.
пн 13.04.2020 - дома решать олимпиаду ИОИП 25.03.2012 на сайте https://codeforces.c.../101289/virtual + 17.05-19.05 Codeforces.ru (заранее подайте заявку)
Все олимпиадники, заполните пожалуйста таблицу с вашими данными для олимпиады БГУ
вт 14.04.2020 - дома сделать дорешивание вчерашних Codeforces.ru и олимпиады ИОИП 25.03.2012 по разбору, прикрепленному внизу
ср 15.04.2020 - дома решать олимпиаду ИОИП 25.03.2018 на сайте https://codeforces.c.../101764/virtual + 17.05-19.05 Codeforces.ru (заранее подайте заявку)
чт 16.04.2020 - дома сделать дорешивание вчерашних Codeforces.ru и олимпиады ИОИП 25.03.2018 по разбору, прикрепленному внизу
пт 17.04.2020 - дома решать олимпиаду ИОИП 29.03.2015 на сайте https://codeforces.c.../100716/virtual
сб 18.04.2020 - дома сделать дорешивание олимпиады ИОИП 29.03.2015 по разбору, прикрепленному внизу
вс 19.04.2020 - дома делать дорешку сборов, ЗКШ , прошлых олимпиад, решать Респы прошлых лет, решать задачи с архива Codeforces.ru.

вт 21.04.2020 - дома Сodeforces.ru 17.35
чт 23.04.2020 - дома Гомельская областная олимпиада 9.00-14.00 dl.gsu.by + Codeforces.ru 17.35
сб 25.04.2020 - дома олимпиада БГУ 10.00-15.00 https://acm.bsu.by/c.../106/standings/ (логины-пароли вышлю личным сообщением)
вс 26.04.2020 - дома Сodeforces.ru 17.35
пн 27.04.2020 - в гимназии 8 9.00-14.00 тренировочная олимпиада ИОИП 2014 https://codeforces.c...97/virtual/true (приходят только абсолютно здоровые учащиеся с желанием порешать задачи, остальные решают дома). Разбор скачать тут
пт 01.05.2020 - дома Codeforces.ru 17.35
cб 02.04.2020 - дома тренировочная олимпиада на сайте https://codeforces.c...44/virtual/true
вс 03.05.2020 - дома Codeforces.ru 17.35
вт 05.05.2020 - дома тренировочная олимпиада на сайте https://codeforces.c...76/virtual/true
ср 06.05.2020 - дома Codeforces.ru 17.35
чт 07.05.2020 - https://codeforces.c...18/virtual/true
сб 09.05.2020 - дома Codeforces.ru 15.35
сб 16.05.2020 - дома Codeforces.ru 14.35
вс 17.05.2020 - дома Codeforces.ru 12.05
сб 23.05.2020 -
Вседомашняя олимпиада по программированию 2020, первый тур (альтернатива Всероссийской олимпиады 2020)
https://codeforces.c...95/virtual/true

сб 30.05.2020 -
Вседомашняя олимпиада по программированию 2020, второй тур (альтернатива Всероссийской олимпиады 2020)
https://codeforces.c...96/virtual/true

вт 02.06.2020 - командная олимпиада 8-9 классов в Гимназии 1 каб 303 10.30-13.30 https://codeforces.c...25/virtual/true
ср 03.06.2020 - командная олимпиада 8-9 классов в Гимназии 1 каб 303 10.00-13.00 https://codeforces.c...23/virtual/true
пт 05.06.2020 - командная олимпиада 8-9 классов в Гимназии 1 каб 303 10.00-13.00 https://codeforces.c...49/virtual/true
вс 07.06.2020 - личная олимпиада (отбор на Мозырьскую олимпиаду). Очные участники приходят в Гимназию 8 к 11.30, остальные решают дома. Олимпиада проходит с 12.00 до 17.00.
вт 09.06.2020 - командная олимпиада 8-9 классов в Гимназии 8 каб 323 10.00-13.30 https://codeforces.c.../102025/virtual
ср 10.06.2020 - командная олимпиада 8-9 классов в Гимназии 8 каб 325 10.00-13.30 https://codeforces.c.../102023/virtual
чт 11.06.2020 - личная олимпиада VitebskOpen 7-8 в Гимназии 8 каб 325 09.00-14.30
пт 12.06.2020 - в Гимназии 8 09.00-14.00 личная олимпиада 9-10 классов тур 1 VitebskOpen
сб 13.06.2020 - в Гимназии 8 09.00-14.00 личная олимпиада 9-10 классов тур 2 VitebskOpen
вс 14.06.2020 - Мозырьская олимпиада для 7-8 классов