1
Разбор подготовил ученик 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
