fork download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7.  
  8. // Сортировка вставками на итераторах
  9. template<class Iterator, class Comparator>
  10. void insertionSort(Iterator begin, Iterator end, Comparator cmp) {
  11.     // Инвариант: на полуинтервале [begin, sortedEnd) последовательность уже
  12.     // отсортирована.
  13.     //
  14.     // std::next делает копию итератора, сдвинутую на 1 вперёд.
  15.     // это отличается от ++ тем, что ++ меняет исходный итератор, а это — нет.
  16.     // std::prev аналогично двигает копию назад.
  17.  
  18.     for (Iterator sortedEnd = std::next(begin); sortedEnd != end; ++sortedEnd) {
  19.         // Нужно найти место для вставки *sortedEnd в полуинтервал [begin,
  20.         // sortedEnd) Хотим получить итератор на место, _на которое_ нужно будет
  21.         // переставить *sortedEnd. Это отличается от варианта с лекции: там
  22.         // искалось место, _после которого_ ставился новый элемент.
  23.         Iterator insertPosition = begin;
  24.         while (insertPosition != sortedEnd && cmp(*insertPosition, *sortedEnd)) {
  25.             ++insertPosition;
  26.         }
  27.  
  28.         // hint: так как последовательность сортированная, ровно то же самое
  29.         // можно было получить стандартной функцией бинарного поиска, которую
  30.         // тоже можно использовать:
  31.         // insertPosition = std::lower_bound(begin, sortedEnd, *sortedEnd, cmp);
  32.  
  33.         // Теперь хотим сдвинуть полуинтервал [insertPosition, sortedEnd) на
  34.         // одну позицию вправо, чтобы поставить в insertPosition старое
  35.         // значение *sortedEnd. Например, это можно сделать так:
  36.         typename std::iterator_traits<Iterator>::value_type insertValue = *sortedEnd;
  37.         for (Iterator it = sortedEnd; it != insertPosition; --it) {
  38.             *it = *std::prev(it);
  39.         }
  40.         *insertPosition = insertValue;
  41.  
  42.         // hint: то, что сейчас произошло — это циклический сдвиг полуинтервала
  43.         // [insertPosition, std::next(sortedEnd)) на одну позицию право. Для
  44.         // этого есть стандартная функция, которую тоже можно было использовать:
  45.         // std::rotate(insertPosition, sortedEnd, std::next(sortedEnd));
  46.     }
  47. }
  48.  
  49.  
  50. // Упражнение 1: является ли получившаяся сортировка стабильной? Что нужно
  51. // сделать, чтобы она стала стабильной?
  52.  
  53. // Упражнение 2 (со звёздочкой из-за необходимости почитать-таки документацию о
  54. // стандартной библиотеке, см. ссылки справа): А при использовании стандартных
  55. // алгоритмов?
  56.  
  57.  
  58. // Перейдём к решению задачи 1.3, она интересная.
  59.  
  60. struct Point {
  61.     // Конструктор без аргументов, так называемый default constructor.
  62.     // Если его не определить, но определить какие-то другие конструкторы,
  63.     // не получится завести переменную, не инициализировав её, а для
  64.     // создания вектора из n точек это нужно.
  65.     Point() {
  66.         x = -1;
  67.         y = -1;
  68.     }
  69.  
  70.     // Конструктор от координат
  71.     Point(int x_, int y_) {
  72.         x = x_;
  73.         y = y_;
  74.     }
  75.  
  76.     // Конструктор точки, радиус-вектор которой указывает из точки a в точку b:
  77.     Point(const Point& a, const Point& b) {
  78.         x = b.x - a.x;
  79.         y = b.y - a.y;
  80.     }
  81.  
  82.     int x, y;
  83. };
  84.  
  85. bool lexicographicalLess(const Point& a, const Point& b) {
  86.     return (
  87.         a.x != b.x  // если точки не равны по x,
  88.         ? a.x < b.x // сравнить по x,
  89.         : a.y < b.y // иначе сравнить по y.
  90.     );
  91. }
  92.  
  93. // Класс-компаратор, запоминающий точку, поворот относительно которой будет
  94. // проверяться. Рекомендую сначала прочитать комментарии в main.
  95. struct PositiveRotationChecker {
  96.     PositiveRotationChecker(const Point& pivotPoint_) {
  97.         pivotPoint = pivotPoint_;
  98.     }
  99.  
  100.     // Перегрузка оператора (), благодаря которой _экземпляры_ этого класса
  101.     // можно вызывать как функции. При таком вызове на самом деле будет
  102.     // исполняться тело этого перегруженного оператора.
  103.     //
  104.     // Стандартные алгоритмы вызывают компараторы с аргументами типа const T&,
  105.     // поэтому пару сравниваемых точек мы должны принимать
  106.     // либо как (Point, Point), либо как (const Point&, const Point&).
  107.     bool operator() (const Point& a, const Point& b) {
  108.         // Проведём радиус-векторы из pivotPoint в a и в b. Такие два способа
  109.         // инициализации эквивалентны, в обоих просто вызывается конструктор
  110.         // Point(const Point&, const Point&).
  111.         Point radiusA = Point(pivotPoint, a);
  112.         Point radiusB(pivotPoint, b);
  113.  
  114.         // Первое, что приходит в голову — посмотреть на полярные углы двух
  115.         // векторов из точек, и сравнить их. Полярный угол легко узнать как
  116.         // арктангенс отношения ординаты и абсциссы, для этого есть специальная
  117.         // функция atan2:
  118.         bool atan2Check = std::atan2(radiusA.y, radiusA.x) > std::atan2(radiusB.y, radiusB.x);
  119.  
  120.         // Это будет работать, но не оптимально сразу по нескольким причинам.
  121.         // atan2 — довольно тяжёлая операция, внутри считаются какие-то ряды, в
  122.         // результате получается вещественное число с какой-то погрешностью,
  123.         // хотя у нас целочисленные координаты, и вполне возможно было бы
  124.         // сделать точное сравнение.
  125.         // Поэтому воспользуемся исключительно полезным свойством векторного
  126.         // произведения двух векторов из R2: его z-координата равна
  127.         // произведению длин векторов и синуса ориентированного угла между
  128.         // ними. Фактически то, что мы хотим проверить — положительность
  129.         // поворота от одного вектора к другому —, равносильна положительности
  130.         // этого синуса. Поэтому можно просто посчитать z-координату векторного
  131.         // произведения, и посмотреть не её знак.
  132.         bool crossProductCheck = (0 > radiusA.x * radiusB.y - radiusB.x * radiusA.y);
  133.  
  134.         // Вообще-то должно получиться одно и то же.
  135.         assert(atan2Check == crossProductCheck);
  136.  
  137.         return crossProductCheck;
  138.     }
  139.  
  140.     Point pivotPoint;
  141. };
  142.  
  143.  
  144. int main() {
  145.     size_t n;
  146.     std::cin >> n;
  147.  
  148.     std::vector<Point> points(n);
  149.     for (Point& point : points) {
  150.         std::cin >> point.x >> point.y;
  151.     }
  152.  
  153.     // Найдём точку, минимальную сначала по x, затем по y:
  154.     // std::min_element — Стандартная функция, ищет минимальный элемент в
  155.     // полуинтервале между итераторами, возвращает итератор. Компаратор, как
  156.     // обычно, опционален.
  157.     std::vector<Point>::iterator minIter = std::min_element(
  158.         points.begin(), points.end(),
  159.         lexicographicalLess
  160.     );
  161.  
  162.     // Переставим минимальный элемент в начало:
  163.     // Почти равносильно std::swap(points[0], *minIter)
  164.     // или std::swap(points[0], points[minIter - points.begin()])
  165.     std::iter_swap(points.begin(), minIter);
  166.  
  167.     // Теперь хочется отсортировать остальные точки по полярному углу
  168.     // относительно точки points[0]. То есть точка A должна идти раньше точки
  169.     // B, если поворот от вектора из points[0] в A к вектору из points[0] в B
  170.     // совершался, скажем, против часовой стрелки.
  171.     // Если мы так сделаем, получится ломаная, удовлетворяющая требованиям.
  172.     //
  173.     // Получается, что для такого сравнения точек A и B компаратору нужно
  174.     // знать ещё и points[0], а компаратор это обычно функция, принимающая всего
  175.     // два аргумента. Что же делать?
  176.     //
  177.     // В этой задаче есть два способа справиться с проблемой:
  178.     //
  179.     // 1. Перед сортировкой перенести начало координат в точку points[0].
  180.     // В компараторе смотреть на поворот относительно начала координат.
  181.     // Вполне рабочее решение, кажется, не нуждающееся в комментарии.
  182.     //
  183.     // 2. Описать компаратор, представляющий из себя не функцию, а класс, в
  184.     // котором сохранена точка points[0], и который за счёт перегрузки оператора
  185.     // operator() можно вызывать как функцию. Его реализацию см. выше.
  186.     PositiveRotationChecker comparator(points[0]);
  187.     insertionSort(points.begin() + 1, points.end(), comparator);
  188.  
  189.     // Готово, вы великолепны, можно выводить ответ:
  190.     for (const Point& point : points) {
  191.         std::cout << point.x << ' ' << point.y;
  192.         std::cout << '\n';
  193.     }
  194.     std::cout << '\n';
  195.  
  196.     // Такой цикл (этот синтаксис называется range-based for) тоже устроен на
  197.     // итераторах, и без них бы не работал. Этот синтаксис преобразуется вот в
  198.     // такой обычный for:
  199.     for (
  200.         // Запоминаются две переменные: текущий итератор и итератор на конец
  201.         // контейнера.
  202.         // std::begin(points) — это то же самое, что points.begin(), то есть
  203.         // итератор на начало контейнера. Тем не менее, std::begin будет
  204.         // работать даже для статических массивов, у которых нет методов.
  205.         std::vector<Point>::iterator it = std::begin(points), end = std::end(points);
  206.         it != end;
  207.         ++it
  208.     ) {
  209.         const Point& point = *it;
  210.  
  211.         // Далее тело range-based for'а:
  212.         std::cout << point.x << ' ' << point.y;
  213.         std::cout << '\n';
  214.     }
  215.     std::cout << '\n';
  216.  
  217.     // Если вам нужно просто пробежаться по контейнеру, а номера позиций или
  218.     // итераторы не нужны, предпочтительно использовать range-based for.
  219. }
  220.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5
5 2
2 4
3 -3
2 2
4 4
stdout
copy 
2 2
2 4
4 4
5 2
3 -3

2 2
2 4
4 4
5 2
3 -3
https://ideone.com/haJ71Y
see:

http://r...content-available-to-author-only...e.com/w/cpp/numeric/math/atan2

http://r...content-available-to-author-only...e.com/w/cpp/algorithm/min_element

http://r...content-available-to-author-only...e.com/w/cpp/algorithm/rotate

http://e...content-available-to-author-only...e.com/w/cpp/algorithm/lower_bound
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!