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