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


LVP

Регистрация: 21 Dec 2011
Offline Активность: 21 Sep 2021 18:10
*****

Мои темы

расписание август-сентябрь 2021

24 August 2021 - 21:55

расписание август-сентябрь 2021 (следите за изменениями)

вт 24.08.2021 - 9.30-14.30 тренировочная командная олимпиада: https://codeforces.c.../103113/virtual

ср 25.08.2021 - 9.30-14.30 тренировочная командная олимпиада:
усложненный уровень: https://codeforces.c.../100516/virtual
разбор: http://neerc.ifmo.ru...25-advanced.pdf

базовый уровень (на 3 часа): https://codeforces.c.../100515/virtual
разбор: http://neerc.ifmo.ru...41025-basic.pdf

чт 26.08.2021 - 9.30-14.30 тренировочная командная олимпиада:
усложненный уровень https://codeforces.c.../101619/virtual
разбор: http://neerc.ifmo.ru...26-advanced.pdf

базовый уровень (на 3 часа): https://codeforces.c.../101618/virtual
разбор: http://neerc.ifmo.ru...71126-basic.pdf

пт 27.08.2021 - 9.30-14.30 тренировочная командная олимпиада (решить надо все!!!)
усложненная: https://codeforces.c.../100252/virtual
базовая: https://codeforces.c.../100251/virtual

пн 30.08.2021 - 9.00-14.00 тренировочная командная олимпиада: https://codeforces.c.../100029/virtual (делайте дома дорешку!!!)

вт 31.08.2021 - 08.45-14.00 тренировочная командная олимпиада: https://codeforces.c.../100161/virtual (делайте дома дорешку!!!)

Зарегистрируйтесь на Зеркало личной Минской олимпиады (10 класс тоже может участвовать). Отбор 09.09, финал 23.09 (15.00-18.00)
Регистрация участника зеркала VI личного первенства г. Минска по программированию среди учащихся VI-IX классов учреждений общего среднего образования
https://docs.google....eLQq_g/viewform

сб 04.09.2021 - 11.00-16.00 в Гимназии 8 тренировочная командная олимпиада: https://codeforces.c.../100594/virtual

вс 05.09.2021 - дома решать Codeforces.ru 17.35

сб 11.09.2021 - 11.00-16.00 в Гимназии 8 тренировочная командная олимпиада
https://codeforces.c.../101445/virtual
вс 12.09.2021 - дома решать 17.35 -20.05 Codeforces.ru

сб 18.09.2021 - 10.00-15.00 в Гимназии 8 тренировочная командная олимпиада https://codeforces.c.../101225/virtual + дома 17.35 Codeforces/ Делать дорешку!!!!!
вс 19.09.2021 - 11.00-16.00 в Гимназии 8 командная олимпиада Opencup.cup

Зарегистрируйтесь на Олимпиаду во ВШЭ:
https://olymp.hse.ru/mmo/it

сб 25.09.2021 - 12.00-16.00 в Гимназии Гомельская областная олимпиада http://contest.yandex.ru/CYF
вс 26.09.2021 - 11.00-16.00 в Гимназии 8 командная олимпиада Opencup.cup

Задача Монстры

07 March 2021 - 20:33

Задача Монстры (III Всероссийская командная олимпиада).
Разбор подготовил ученик 8 класса Гимназии 1 г.Витебска Захаренков Захар.

#include <bits/stdc++.h>
#define endl '\n'
#define S second
#define F first
#define pb push_back
#define ll long long
#define ull unsigned long long
#define pii pair <ll , ll>
using namespace std;
const ll mod = (1e9) + 7;
const int N = 2002;
const int M = 50009;
bool u[1010];//
pair <pii , pii> r[1010];// массив для хранения отрезков.
bool gor(int i)
{
	return (r[i].F.S == r[i].S.S);// если отрезки горизонтальные, то их у-ки точно не будут меняться.
}
bool ver(int i)
{
	return (r[i].F.F == r[i].S.F);// если отрезки горизонтальны, то их х-ы точно не будут меняться.
}
bool odnagor(int i , int j)
{
	return (gor(i) && gor(j) && r[i].F.S == r[j].F.S);// если отрезки горизонтальны, и они на одной горизонтали, то их у-ки будет равны.
}
bool odnaver(int i , int j)
{
	return (ver(i) && ver(j) && r[i].F.F == r[j].F.F);// если отрезки вертикальны, и они на одной вертикали, то их х-ы будут равны.
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
	#ifdef LOCAL
  freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
#endif
int n , m , k;
cin >> n >> m >> k;
	swap(n , m);// так как нам вводят m на n.
for(int i = 0;i < k;++ i)
	{
    	int x , y;
    	char by;
    	cin >> x >> y >> by;
    	// Давайте преобразуем наших монстриков в отрезки.
    	// Обусловимся, что восток - отрезок направлен вправо, запад - отрезок напрвлен влево, север - отрезок направлен вверх, юг - отрезок направлен вниз.
    	// в решении мы используем декартову прямоугольную систему координат на плоскости.
    	// Отрезки мы будем хранить следующим образом:
    	// r[i].F.F - координата начала по x.
    	// r[i].F.S - координата начала по у.
    	// r[i].S.F - координата конца по x.
    	// r[i].F.S - координата конца по у.
    	// Для решения этой задачи нам важно знать, где начало, а где конец. Пусть если отрезок горизонтальный, то по у он изменяться не будет, а левая точка по х это его r[i].F.F.
    	// Вертикальные отрезки изменяются только по y, тогда r[i].F.S - нижняя точка.
    	// про структуру switch можно почитать вот тут: http://easy-code.ru/lesson/switch-case-cpp
    	switch(by)
    	{
        	case 'E' :
            	r[i].F.F = x;
            	r[i].F.S = y;
            	r[i].S.F = m;
            	r[i].S.S = y;
            	break;
        	case 'W' :
            	r[i].F.F = 1;
            	r[i].F.S = y;
            	r[i].S.F = x;
            	r[i].S.S = y;
            	break;
        	case 'N' :
            	r[i].F.F = x;
            	r[i].F.S = y;
            	r[i].S.F = x;
            	r[i].S.S = n;
            	break;
        	case 'S' :
            	r[i].F.F = x;
            	r[i].F.S = 1;
            	r[i].S.F = x;
            	r[i].S.S = y;
            	break;
    	}
	}
	// Двайте рассмотрим случай, когда два монстрика смотрят друг на друга и заменим отрезок одного из них на отрезок длиной во весь столбик или строку,
	// давайте опишем относительно друг друга отрезки образованные этими монстриками.
	// 1) эти отрезки должны на одной вертикали или горизонтали.
	// 2) из первого пункта следует, что их координаты будут изменяться только по х или только по у.
	// 3) если мы сложим длины этих кусочков, то полученная сумма будет точно больше или равна(длине строки или длине столбика).
	//	из этого вытекает, что для горизонтальных верно следующее неравенство: r[i].S.F >= r[j].F.F
	//	и для вертикальных: r[i].S.S >= r[j].F.S
	//	это можно было расписать через сумму длин, но суть не меняется.Так как мы просто доказываем, есть место где наши отрезки накладываются друг на друга.
	// 4) если смотреть на начало одного отрезка, оно будет равно 1, а конец другого будет n или m.
	// Давайте напишем это.
	for(int i = 0;i < k;++ i)// перебираем первый отрезок
	{
    	for(int j = 0;j < k;++ j)// перебираем второй отрезок, так как k <= 1000, то можно заквадрат.
    	{
        	if(i == j)// не смысла проверять одинаковые отрезки.
        	{
            	continue;// continue пропускает все дальнейшие действия в цикле.
        	}
        	if(odnagor(i , j) && r[i].F.F == 1 && r[j].S.F == m && r[i].S.F >= r[j].F.F)// мы проверяем 1 и 4 пункт для горизонтальных отрезков.
        	{
            	r[i].S.F = m;// так как начало i-того отрезка находится в 1, то чтобы сделать на всю строку перенесём его конец в m.
        	}
        	if(odnaver(i , j) && r[i].F.S == 1 && r[j].S.S == n && r[i].S.S >= r[j].F.S)// проверяем 1 и 4 пункт для вертикальных отрезков.
        	{
            	r[i].S.S = n;// и сделаем наш i-ый отрезок на весь столбик(перенесём конец в n).
        	}
    	}
	}
	// дальще мы можем заметить, что отрезки которые находятся полностью внутри какого-то отрезка на ответ влиять не должны.
	// опишем некоторый массив u[k], в котором u[i] указывает важен этот отрезок, тогда u[i] = 0.
	//                                          	или этот отрезок можно убрать u[i] = 1.
	// давайте посмотрим какими свойствами обладают такие отрезки.
	// 1) они явно на одной вертикаль или горизонтали.
	// 2) они направлены в одну сторону.
	// 3) они изменяются только по х или только у.
	// 4) мы будем оставлять нужным отрезок с большей длиной.
	for(int i = 0;i < k;++ i)// перебираем первый отрезок
	{
    	for(int j = 0;j < k;++ j)// перебираем второй отрезок
    	{
        	if(i == j || u[i] || u[j])// проверяем, что нам попались разные отрезки, и они там ещё нужны.
        	{
            	continue;// continue - пропускает все дальнейшие действия в цикле.
        	}
        	if(odnagor(i , j))// проверяем пункт 1.
        	{
            	ll s1 = abs(r[i].S.F - r[i].F.F) + 1;// считаем длину i-того отрезка.
            	ll s2 = abs(r[j].S.F - r[j].F.F) + 1;// считаем длину j-того отрезка.
            	if(r[i].F.F == 1 == r[j].F.F || r[i].S.F == r[j].S.F)// рассмотрим 2 случая:1) если отрезки направлены влево, то их начальные x-ы равны единице.
            	{                                                             			//2) если отрезки направлены вправо, то их конечные х-ы равны.
                	if(s1 >= s2)// выполняем 4 пункт.
                	{
                    	u[j] = 1;
                	}
                	else
                	{
                    	u[i] = 1;
                	}
            	}
        	}
        	if(odnaver(i , j))// проверяем пункт 1.
        	{
            	ll s1 = abs(r[i].S.S - r[i].F.S) + 1;// считаем длину i-того отрезка.
            	ll s2 = abs(r[j].S.S - r[j].F.S) + 1;// считаем длину j-того отрезка.
            	if(r[i].F.S == 1 == r[j].F.S || r[i].S.S == r[j].S.S)// рассмотрим 2 случая:1) если отрезки направлены вниз, то их начальные у-ки равны единице.
            	{                                                             			//2) если отрезки направлены вверх, то их конечные у-ки равны.
                	if(s1 >= s2)// выполняем 4 пункт.
                	{
                    	u[j] = 1;
                	}
                	else
                	{
                    	u[i] = 1;
                	}
            	}
        	}
    	}
	}
	ll ans = 0;// это наша итоговая сумма(ответ). вообще максимальный ответ примерно 1е9, но для подстраховки можно сделать его лонговским.
	for(int i = 0;i < k;++ i)
	{
    	ans += (1 - u[i]) * ((r[i].S.F - r[i].F.F + 1) * (r[i].S.S - r[i].F.S + 1));//((r[i].S.F - r[i].F.F + 1) * (r[i].S.S - r[i].F.S + 1)) - это площадь i-того отрезка.
    	// если отрезок нужен u[i] = 0, тогда 1 - u[i] = 1, следовательно произведение будет равно площади отрезка(его длине).
    	// напротив при u[i] = 1, произведение будет равно 0 и длина отрезка не будет засчитана.
	}
	// остаётся последний шаг, нам надо посчитать количество точек, в которых пересекаются один вертикальный отрезок и один горизонтальный отрезок.
	// распишем, что происходит.
	// 1) эти отрезки нам нужны.
	// 2) i-ый отрезок горизонтальный, а j-ый отрезок вертикальный.
	// 3) и выполняется следующие неравенства r[i].F.F <= r[j].F.F && r[j].F.F <= r[i].S.F и r[j].F.S <= r[i].F.S && r[i].F.S <= r[j].S.S.
	for(int i = 0;i < k;++ i)// перебор i-того отрезка
	{
    	for(int j = 0;j < k;++ j)// перебор j-того отрезка
    	{
        	if(i == j || u[i] || u[j])// проверяем, что нам попались разные отрезки и они нам нужны.
        	{
            	continue;// continue - пропускает все дальнейшие действия в цикле.
        	}
        	if(gor(i) && ver(j) && (r[i].F.F <= r[j].F.F && r[j].F.F <= r[i].S.F) && (r[j].F.S <= r[i].F.S && r[i].F.S <= r[j].S.S))// проверяем 2 и 3 пункты.
        	{
            	-- ans;// так как эти отрезки пересекаются строго в одной точке и эта точка в ответе посчитана уже 2 раза, то ответ надо уменьшить на 1.
        	}
    	}
	}
	cout << ans;// вывод ответа.
return 0;
}


Сдать задачу можно на сайте: https://informatics....chapterid=536#1

расписание январь-май 2021

04 January 2021 - 12:35

расписание январь-май 2021 (следите за изменениями)

Сборы по подготовке к областной олимпиаде 09.00-16.00:
28.12, 29.12, 30.12, 04.01, 05.01, 06.01, 08.01, 09.01

ПРОГРАММА проведения третьего этапа республиканской олимпиады
по информатике 11 – 14 января 2021 года
Место проведения: УО ”Полоцкий государственный университет“ (г. Полоцк, Стрелецкая, 4)
Место проживания и питания: УО ”Полоцкий государственный химико-технологический колледж“ (г. Полоцк, Вильнюсское шоссе, д. 10).

11 января 2021 г.
14.10 Сбор на ж/д вокзале около входа в кассы пригородных поездов. Приготовить за билет 2.40руб. С собой взять ПАСПОРТ, справку от врача для заселения в общежитие и копию 1 страницы устава школы, 10 масок, банку антисептика, 3 пары перчаток на туры, деньги для личных трат, справку что ученик (для проезда в общественном транспорте) . Обязательно пообедать! Захватить чай, печеньки, кипятильник и кружку, удачу и спокойствие.
17.00 – 19.00 Проведение пробного тура (УО ”Полоцкий государственный университет“)
19.00 – 19.30 Ужин (столовая общежития УО ”Полоцкий государственный химико-технологический колледж“)
19.30-21.30 Заезд, регистрация и размещение участников олимпиады (общежитие УО ”Полоцкий государственный химико-технологический колледж“)
22.00 Отбой (глубокий сон)

12 января 2021 г.
7.00 Подъем
7.30 – 8.00 Завтрак (столовая общежития УО ”Полоцкий государственный химико-технологический колледж“)
9.00 – 14.00 Выполнение олимпиадных заданий І тура (УО ”Полоцкий государственный университет“)
14.30 – 15.30 Обед (столовая УО ”Полоцкая государственная гимназия №1 имени Ф.Скорины“)
15.30 – 18.00 Отдых
18.00 – 19.00 Ужин (столовая общежития УО ”Полоцкий государственный химико-технологический колледж“)
19.00 -21.30 Отдых
22.00 Отбой (глубокий сон)

13 января 2021 г.
7.00 Подъем
7.30 – 8.00 Завтрак (столовая общежития УО ”Полоцкий государственный химико-технологический колледж“)
9.00 – 14.00 Выполнение олимпиадных заданий ІІ тура (УО ”Полоцкий государственный университет“)
14.30 – 15.30 Обед (столовая столовая УО ”Полоцкая государственная гимназия №1 имени Ф.Скорины“)
16.00 – 18.00 Проведение самотестирования, ознакомление с работами участников и результатами их оценивания (УО ”Полоцкий государственный университет“)
18.00 – 18.30 Ужин (столовая общежития УО ”Полоцкий государственный химико-технологический колледж“)
18.00 – 21.30 Отдых (для участников олимпиады)
22.00 Отбой (глубокий сон)

14 января 2021 г.
7.30 Подъем
8.00 – 8.30 Завтрак
8.30 – 9.10 Сбор личных вещей для отъезда
9.15 - выход с личными вещами из общежития. Сумки с вещами погружаем в маленький жёлтый автобус, а сами садимся в большие зеленые автобусы
9.45 - 11.00 Разбор авторских решений задач с участниками олимпиады (УО ”Полоцкий государственный университет“)
11.30 – 12.30 - Награждение победителей (УО ”Полоцкий государственный университет“)
13.30 – 14.00 Обед (столовая УО ”Полоцкая государственная гимназия №1 имени Ф.Скорины“)
14.20 Отъезд команды (дизель в 14.59, прибытие в Витебск в 17.04)

сб 16.01.21 - в Гимназии 8 тренировочная командная олимпиада 11.00-16.00 https://codeforces.c.../102904/virtual /

Зарегистрируйтесь дома на МОШ и РЕШАЙТЕ: http://mos-inf.olimp...info_olymp10-11 , http://mos-inf.olimp...u/info_olymp6-9

Зарегистрируйтесь на ЗКШ: https://it-edu.com/m...s-juniors-2021/
Информацию о датах туров смотрите тут: https://it-edu.com/r...%D0%B0/mwj2021/

Зарегистрируйтесь на личные Питерские олимпиады: http://neerc.ifmo.ru...rIndividual.jsp

сб 23.01.21 - в Гимназии 8 личная Американская олимпиада 11.00-16.00 (желательно дойти до Платины или хотя бы до Золота): http://usaco.org/ind...p?page=contests (дома в воскресенье 24.01.2021 дорешивать)
вс 24.01.21 - дома 12.00-16.00 решать отбор в ЗКШ https://it-edu.com/r...%D0%B0/mwj2021/

сб 30.01.21 - 11.00-16.00 личная олимпиада в Гимназии 8 https://codeforces.c.../102935/virtual
Разбор прикреплен ниже.

Для завтрашней олимпиады обязательно заранее зарегистрируйтесь на сайте: https://neerc.ifmo.r...rIndividual.jsp
вс 31.01.21 - дома 12.00-16.00 решать отбор в ЗКШ https://it-edu.com/r...%D0%B0/mwj2021/ + 16.00-21.00 дома личная Питерская олимпиада (для 11 классов - это отбор на ИОИП https://neerc.ifmo.r...l/io/index.html

СБОРЫ ПО ПОДГТОВКЕ К РЕСПУБЛИКАНСКОЙ ОЛИМПИАДЕ 2021 (следите за изменениями в расписании):
пн 01.02.2021 - 325 кабинет Гимназия 8 9.00-17.15
вт 02.02.2021 - 325 кабинет Гимназия 8 9.00-17.00
ср 03.02.2021 - 325 кабинет Гимназия 8 9.00-17.00
чт 04.02.2021 - 325 кабинет Гимназия 8 11.00-18.00
пт 05.02.2021 - 325 кабинет Гимназия 8 9.00-17.00
сб 06.02.2021 - 325 кабинет Гимназия 8 9.00-15.00
Зарегистрируйтесь на Технокубок:
https://technocup.mail.ru/
вс 07.02.2021 - дома решать ЗКШ 12.00-16.00
пн 08.02.2021 - 325 кабинет Гимназия 8 12.00-18.00
вт 09.02.2021 - 325 кабинет Гимназия 8 9.00-17.00
ср 10.02.2021 - 325 кабинет Гимназия 8 9.00-17.00
чт 11.02.2021 - 325 кабинет Гимназия 8 11.00-18.00
пт 12.02.2021 - 325 кабинет Гимназия 8 9.00-17.00
сб 13.02.2021 - 325 кабинет Гимназия 8 09.00-15.00
+ дома решать 16.00-21.00 личную Питерскую олимпиаду https://neerc.ifmo.r...l/io/index.html
вс 14.02.2021 - 11.00-16.00 в гимназии 8 командная олимпиада opencup.ru (Гран при Беларуси)
Команды:
Vitebsk01: Смирнов+Тилигузов+Гнедько
Vitebsk02: Адаменко+Новицкий+Балюконис
Vitebsk03: Яцук+Грунтов+Патрушева
Vitrbsk04: Заровский+Бовбель+Борчук
Vitebsk05: Бельский+Рубиш+Козлова
Vitrbsk06: Луценко+Горячкина+Хритоненко
Vitebsk07: Соколовская+Ильина+Андреева
Vitebsk08: Зимницкий+Кускова+Захаренков
Vitebsk09: Кузьмичев+Петько+Володченко
После сборов продолжайте изучать (повторять) теорию на https://e-maxx.ru/algo/ и на https://brestprog.by/topics/ , решайте Республики прошлых лет на dl.gsu.by (у кого нет разборов, то подойдите ко мне), решайте на Codeforces или https://informatics....d=39#section-20 Открытки (разборы есть на сайте https://olympiads.ru/zaoch/ ) и Всероссйские прошлых лет https://informatics....e/view.php?id=4 (разборы есть на https://neerc.ifmo.r...hive/index.html ).
Вторая часть сборов планируется с 15.03.21

сб 20.02.2021 - 325 кабинет Гимназия 8 11.00-16.00 тренировочная личная олимпиада https://codeforces.c...17/virtual/true
Дома олимпиаду могут решать те кто прошел на Иннополис и хочет с 12.00 дома пройти пробный тур с прокторингом. Остальных прошу решать в школе.

вс 21.02.2021 - дома финал Иннополис. Кто не прошел, тот дорешивает задачи со сборов наших и Ропана

сб 27.02.2021 - в гимназии 8 решать 9.00-14.00 Американская олимпиада http://usaco.org/ + дома ОБЯЗАТЕЛЬНО второй отбор на ИОИП 15.00-20.00 https://neerc.ifmo.r...l/io/index.html

вс 28.02.2021 - 11.00-16.00 в гимназии 8 командная олимпиада opencup.ru (Гран при Tokyo)

сб 06.03.2021 - 325 кабинет Гимназия 8 11.00-16.00 тренировочная личная олимпиада https://codeforces.c...36/virtual/true (разбор прикреплен внизу). Видеоразбор: https://www.youtube....TB6bzGGiqEV60og

пт 12.03.2021 - участники Открытой олимпиады собираются в кабинете 325 Гимназии 8 в 9.15. С собой можно брать книги, питье, еду.
сб 13.03.2021 - участники Открытой олимпиады собираются в кабинете 325 Гимназии 8 в 9.15. С собой можно брать книги, питье, еду. Остальные дома 12.00-14.30 решают 1 тур Открытой олимпиады https://codeforces.com/contests и готовятся к сборам (повторяют теорию, решают Республики прошлых лет)

пн 15.03.2021 - 9.00-17.00 в Гимназии 8 сборы по подготовке к Республиканской олимпиаде.
вт 16.03.2021 - 9.00-17.00 в Гимназии 8 сборы по подготовке к Республиканской олимпиаде.
ср 17.03.2021 - 9.00-17.00 в Гимназии 8 сборы по подготовке к Республиканской олимпиаде.
чт 18.03.2021 - 9.00-17.00 в Гимназии 8 сборы по подготовке к Республиканской олимпиаде.
пт 19.03.2021 - 9.00-17.00 в Гимназии 8 сборы по подготовке к Республиканской олимпиаде.
сб 20.03.2021 - дома в рамках сборов по подготовке к Республиканской олимпиаде и для подготовки к ИОИП и Технокапу решать личную олимпиаду:https://codeforces.com/gymRegistration/101820/virtual/true
Разбор задач: http://neerc.ifmo.ru...vidual-hard.pdf

Каждый день до Республиканской олимпиады решать Всероссийские личные и Открытые олимпиады прошлых лет на CF или informatisc:
https://informatics....e/view.php?id=4
https://informatics....d=39#section-18
делать дорешку и читать разборы тут: https://neerc.ifmo.r...hive/index.html и https://olympiads.ru/zaoch/
С 22.03 по 26.03 в 11.00-16.00 решайте тренировочный контест на
http://contest.yandex.ru/CYF

сб 27.03.2021 - 9.00-14.00 в Гимназии 8 тренировочная личная олимпиада на сайте http://contest.yandex.ru/CYF
вс 28.03.2021 - в Гимназии 8 для 11 классов личная олимпиада ИОИП. Приходить в 325 кабинет к 10.15.Тур с 11.00-15.00 (4 часа)

сб 10.04.2021 - 11.00 - 16.00 Командная тренировочная олимпиада: https://codeforces.c...35/virtual/true

Составы команд:
Балюконис+Рубиш+Козлова
Гнедько+Ильина+Борчук
Заровский+Андреева+Кузьмичев
Бельский+Патрушева+Горячкина
Несите у кого есть ноутбуки!!!!!

Для подготовки к Международным сборам самостоятельно решать: https://codeforces.c...94/virtual/true и Codeforces!!!!!!

сб 17.04.2021 - 11.00 - 16.00 Командная тренировочная олимпиада:https://codeforces.com/gym/101172/virtual

Составы команд:
Балюконис+Рубиш+Бельский (тренер Грунтов)
Гнедько+ Заровский +Борчук (тренер Грунтов)
Андреева + Ильина + Кузьмичев (тренер Яцук)
Патрушева + Козлова + Горячкина (тренер Тилигузов)
Володченко+Петько+Зимницкий (тренер Бовбель)

Станкевич+Цветковская + Гусев+Фролов (тренер Смирнов)
Николаева+Константинова + Шимко+Щекотова (тренер Новицкий)
Кускова+Балюконис + Ушаков+Захаренко (тренер Адаменко)
Волков+Кацук + Соболенко+Высоцкий (тренер Луценко)

Несите у кого есть ноутбуки!!!!!

Зарегистрируйте команды для участия в командной олимпиаде ВШЭ на сайте https://olymp.hse.ru/coding/
Балюконис+Рубиш+Бельский
Гнедько+ Заровский +Борчук
Андреева + Ильина + Кузьмичев
Патрушева + Козлова + Горячкина
Володченко+Петько+Зимницкий
Станкевич+Цветковская +Фролов
Шимко + Соболенко +Ушаков
Николаева+Константинова +Щекотова
Кускова+Балюконис + Захаренков
Волков+Кацук + Высоцкий

сб 24.04.2021 - 11.00 - 16.00 Командная тренировочная олимпиада: https://codeforces.c.../101154/virtual
Состав команд с тренерами остается прежним, как за 17.04.21

29 апреля, в четверг, на contest.yandex.ru/CYF пройдёт зеркало третьего этапа областной олимпиады школьников IV-IX классов по информатике. Будут открыты три дивизиона : 1-4 классы, 5-7 классы, 8-9 классы.

Начало в 11:00, длительность 5 часов.

сб 08.05.2021 - 11.00-14.30 в Гимназии 8 тренировочная командная олимпиада на одном компьютере для подготовки к ВШЭ и Турниру Архимеда. 11-классников прошу тоже прийти к своим детям.
https://codeforces.c.../101285/virtual

сб 15.05.2021 - 16.30-20.00 в Гимназии 8 командная олимпиада Турнир Архимеда. 11-классников прошу тоже прийти к своим детям.

вс 16.05.2021 - 10.40-15.00 в Гимназии 8 командная олимпиада ВШЭ.

сб 22.05.2021 - 9.00-14.00 в Гимназии 8 VitebskOpen_1 тур 8-10 классы
вс 23.05.2021 - 9.00-15.30 в Гимназии 8 VitebskOpen_2 тур 8-10 классы

сб 29.05.2021 - 09.00-12.00 в Гимназии 8 тренировочная командная олимпиада https://codeforces.c...04/virtual/true
вс 30.05.2021 - 9.00-14.00 в Гимназии 8 VitebskOpen 6-8 классы

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

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