Краткая справка о map

map<int, int> cou; // Объявление cou типа "отображение числа на число"
// Для каждой x координаты массив cou
// будет содержать, сколько было различных точек с такой x-координатой

if (cou[x] == 0) // проверить есть ли х в cou (==0 значит нет)

cou[x] = cou[x] + 1; // инкрементировать значение по ключу x
cou[x] = cou[x] - 1; // декрементировать значение по ключу x

cou.clear(); // инициализируем map нулями

map<int, int> m;
m.size() // количество элементов, которые заносились в map
m.erase( x ); // удалить элемент из map элемент с индексом x
// только после этой операции size уменьшается на 1

maxp=m.begin()->first; // максимальный индекс
maxk=m.begin()->second; // значение по максимальному индексу

minp=m.rbegin()->first; // минимальный индекс
mink=m.rbegin()->second; // значение по минимальному индексу

map<int,int>::iterator im; // итератор
im=m.begin();
maxp=im->first;
maxk=im->second;

map<int,int> H;
map<int,int>::reverse_iterator im; // объявление обратного итератора для map
for (im=H.rbegin(); im!=H.rend(); im++)

map<int, pair <int,int> > BD; // "отображение числа на пару чисел"
map<int, pair <int,int> >::iterator im; // объявление итератора для map

BD[A]=make_pair(B,kk); // число A отображается на пару B,kk

// вывод содержания map вместе номерами в map
i0=1;
for (im=BD.begin(); im!=BD.end(); im++)
  {
    Mon =(*im).first;
    MaxM=(*im).second.first;
    nom =(*im).second.second;
    cout << i0 << ' ' << Mon << ' ' << MaxM << ' ' << nom << endl;
    i0++;
  }

map<int, pair <int,int> > BD10; // Массив MAP
map<int, pair <int,int> >::iterator im; // итератор
BD[nBD][A]=make_pair(B,kk); // присваивание
BD[nBD].erase(A); // удаление
!BD[nBD].empty() // проверка на пустоту
Д[nBD].size() // вычисление размера
for (im=BD[nBD].begin(); im!=BD[nBD].end(); im++) // цикл по всем элементам

map<int,map<int,int> > mat; // объявление mat как отображение пары на число
// хранение "разряжённого" двумерного массива
mat[y][x]=1; // занесение значения в разряжённый массив

map<int,map<int,int> > BD; // объявление BD как отображение пары на число
map<int,map<int,int> >::iterator im; // итератор по первому индексу
map<int,int>::iterator im2; // итератор по второму индексу

BD.clear(); // обнулить двумерный массив BD

BD[A][B]=BD[A][B]+1; // инкрементировать элемент двумерного массива

for (im=BD.begin(); im!=BD.end(); im++)  // двойной цикл по двумерному массиву
  {                                      // проверка массива на симметричность
    A = im->first;
    for (im2 = im->second.begin(); im2 != im->second.end(); im2++)
      {
        B = im2->first;
        C = im2->second;
        if (BD[B][A]!=C) { yes=false; break; };
      }
  };
if (yes) cout << "Yes"; else cout << "No";

map<int,vector<pair<int,int> > >::iterator im; // объявление итератора для map

12_AprB. 3Lines
http://dl.gsu.by/task.jsp?nid=1422499&cid=15

Имеется N (1 <= N <= 50,000), точек с целочисленными координатами
(x_i, y_i) (все в диапазоне 0...1,000,000,000); никакие две точки
не расположены в одной и той же позиции.

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

Формат ввода

• Строка 1: Целое число N.
• Строки 2..1+N: Строка i+1 содержит разделенные пробелом целые числа
  x_i y_i , определяющие координаты точки i.

Формат вывода

• Строка 1: Выведите 1, если существует требуемая тройка прямых,
  и выведите 0 в противном случае.

Пример ввода
6
1 7
0 0
1 2
2 0
1 4
3 4

Пояснения
Всего есть 6 точек, в позициях (1,7), (0,0), (1,2), (2,0), (1,4), (3,4).

Пример вывода
1

Пояснения:
Прямые y=0, x=1, y=4 "покрывают" N точек.

Идея решения:

Фактически требуется узнать, расположены ли все точки на трёх прямых,
параллельных осям координат. Проверим, могут ли они все лежать на трёх
прямых, параллельных оси X или на двух прямых, параллельных оси X
и одной параллельной оси Y (с помощью функции Good), если да -выводим
ответ 1, иначе меняем местами координаты X и Y всех точек и снова
вызываем функцию Good. Соответствующая главная программа выглядит
следующим образом:

int main() {
  freopen("lines.in", "r", stdin);
  freopen("lines.out", "w", stdout);
  cin >> n;
  for(int i = 0; i < n; ++i)
    cin >> lis[i].first >> lis[i].second;
  if (Good()) cout << "1";
    else {
	   for(int i = 0; i < n; ++i)
	     swap(lis[i].first, lis[i].second);
	   if (Good()) cout <<"1";
	     else      cout <<"0";
    	 }
}

В коде ниже используется STL map, чтобы хранить "гистограмму", сколько
раз появилась каждая x-координата, а также общее количество различных
x - координат. Когда точка добавляется в эту структуру данных, этот
счётчик увеличивается (а если количество было равно нулю,
инкрементируется также общее количество различных координат). Когда
точка удаляется из этой структуры данных, счётчик уменьшается, а если
равен нулю - то уменьшается и общее количество различных координат.
Для того, чтобы проверить, могут ли все точки быть покрыты тремя
горизонтальными прямыми, мы добавляем их в нашу структуру
и проверяем что общее количество различных не более 3. Чтобы
проверить, покрываем ли мы всё двумя горизонтальными и одной
вертикальной, мы сортируем точки по x и для каждой x-координаты
временно удаляем все точки с такой x-координатой и проверяем, что
оставшиеся точки имеют не более 2 различных y-координат.

Более подробные пояснения:

pair<int,int> lis[MAXN]; // массив пар координат всех точек
map<int, int> cou; // Для каждой x координаты массив cou
// содержит, сколько было различных точек с такой x-координатой

Функции инкремента и декремента

void inc(int x)
  {
    if (cou[x] == 0) distinct++; // если в cou не было x-координаты,
                                 // то инкрементируем количество различных x-координат
    cou[x] = cou[x] + 1;         // инкрементируем количество точек с координатой x
  }

void dec(int x)
  {
    cou[x] = cou[x] - 1;         // декрементируем количество точек с координатой x
    if(cou[x] == 0) distinct--;  // если колво=0, декремент к-во различных x-координат
  }

Функция Good

sort(lis, lis + n);            // Сортируем по возрастанию x при равенстве x - по y
  distinct = 0;
  cou.clear();                   // инициализируем map нулями
  for (int i = 0; i < n; ++i)
    inc(lis[i].second);          // добавляем точки в map
  if(distinct <= 3) return 1;    // если количество различных x<=3 ответ 1

  int i = 0, i1 = 0;
  while(i < n)                   // перебор по всем точкам
    {
      while(i1 < n && lis[i].first == lis[i1].first) i1++; // считаем в i1 кол-во с
                                                           // текущим одинаковым x
      for(int i2 = i; i2 < i1; ++i2)
	dec(lis[i2].second);         // временно удаляем точки c таким x
      if(distinct <= 2)  return 1;   // если кол-во различных <=2 ответ 1
      for(int i2 = i; i2 < i1; ++i2)
        inc(lis[i2].second);         // возвращаем точки в map
      i = i1;                        // продолжаем с первой точки с другим x
    }
  return 0;
}

Полный текст решения

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;

pair<int,int> lis[MAXN];
map<int, int> cou;
int distinct;
int n;
void inc(int x)
  {
    if(cou[x] == 0) distinct++;
    cou[x] = cou[x] + 1;
  }

void dec(int x)
  {
    cou[x] = cou[x] - 1;
    if(cou[x] == 0) distinct--;
  }

int Good() {
  sort(lis, lis + n);
  distinct = 0;
  cou.clear();
  for(int i = 0; i < n; ++i) inc(lis[i].second);
  if(distinct <= 3) return 1;
  int i = 0, i1 = 0;
  while(i < n)
    {
      while(i1 < n && lis[i].first == lis[i1].first) i1++;
      for(int i2 = i; i2 < i1; ++i2)
	dec(lis[i2].second);
      if(distinct <= 2)  return 1;
      for(int i2 = i; i2 < i1; ++i2) inc(lis[i2].second);
      i = i1;
    }
  return 0;
}

int main() {
  freopen("lines.in", "r", stdin);
  freopen("lines.out", "w", stdout);
  cin >> n;
  for(int i = 0; i < n; ++i)
    cin >> lis[i].first >> lis[i].second;
  if (Good()) cout << "1";
    else {
	   for(int i = 0; i < n; ++i)
	     swap(lis[i].first, lis[i].second);
	   if (Good()) cout <<"1";
	     else      cout <<"0";
	 }
}