#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>
// Сортировка вставками на итераторах
template<class Iterator, class Comparator>
void insertionSort(Iterator begin, Iterator end, Comparator cmp) {
// Инвариант: на полуинтервале [begin, sortedEnd) последовательность уже
// отсортирована.
//
// std::next делает копию итератора, сдвинутую на 1 вперёд.
// это отличается от ++ тем, что ++ меняет исходный итератор, а это — нет.
// std::prev аналогично двигает копию назад.
for (Iterator sortedEnd = std::next(begin); sortedEnd != end; ++sortedEnd) {
// Нужно найти место для вставки *sortedEnd в полуинтервал [begin,
// sortedEnd) Хотим получить итератор на место, _на которое_ нужно будет
// переставить *sortedEnd. Это отличается от варианта с лекции: там
// искалось место, _после которого_ ставился новый элемент.
Iterator insertPosition = begin;
while (insertPosition != sortedEnd && cmp(*insertPosition, *sortedEnd)) {
++insertPosition;
}
// hint: так как последовательность сортированная, ровно то же самое
// можно было получить стандартной функцией бинарного поиска, которую
// тоже можно использовать:
// insertPosition = std::lower_bound(begin, sortedEnd, *sortedEnd, cmp);
// Теперь хотим сдвинуть полуинтервал [insertPosition, sortedEnd) на
// одну позицию вправо, чтобы поставить в insertPosition старое
// значение *sortedEnd. Например, это можно сделать так:
typename std::iterator_traits<Iterator>::value_type insertValue = *sortedEnd;
for (Iterator it = sortedEnd; it != insertPosition; --it) {
*it = *std::prev(it);
}
*insertPosition = insertValue;
// hint: то, что сейчас произошло — это циклический сдвиг полуинтервала
// [insertPosition, std::next(sortedEnd)) на одну позицию право. Для
// этого есть стандартная функция, которую тоже можно было использовать:
// std::rotate(insertPosition, sortedEnd, std::next(sortedEnd));
}
}
// Упражнение 1: является ли получившаяся сортировка стабильной? Что нужно
// сделать, чтобы она стала стабильной?
// Упражнение 2 (со звёздочкой из-за необходимости почитать-таки документацию о
// стандартной библиотеке, см. ссылки справа): А при использовании стандартных
// алгоритмов?
// Перейдём к решению задачи 1.3, она интересная.
struct Point {
// Конструктор без аргументов, так называемый default constructor.
// Если его не определить, но определить какие-то другие конструкторы,
// не получится завести переменную, не инициализировав её, а для
// создания вектора из n точек это нужно.
Point() {
x = -1;
y = -1;
}
// Конструктор от координат
Point(int x_, int y_) {
x = x_;
y = y_;
}
// Конструктор точки, радиус-вектор которой указывает из точки a в точку b:
Point(const Point& a, const Point& b) {
x = b.x - a.x;
y = b.y - a.y;
}
int x, y;
};
bool lexicographicalLess(const Point& a, const Point& b) {
return (
a.x != b.x // если точки не равны по x,
? a.x < b.x // сравнить по x,
: a.y < b.y // иначе сравнить по y.
);
}
// Класс-компаратор, запоминающий точку, поворот относительно которой будет
// проверяться. Рекомендую сначала прочитать комментарии в main.
struct PositiveRotationChecker {
PositiveRotationChecker(const Point& pivotPoint_) {
pivotPoint = pivotPoint_;
}
// Перегрузка оператора (), благодаря которой _экземпляры_ этого класса
// можно вызывать как функции. При таком вызове на самом деле будет
// исполняться тело этого перегруженного оператора.
//
// Стандартные алгоритмы вызывают компараторы с аргументами типа const T&,
// поэтому пару сравниваемых точек мы должны принимать
// либо как (Point, Point), либо как (const Point&, const Point&).
bool operator() (const Point& a, const Point& b) {
// Проведём радиус-векторы из pivotPoint в a и в b. Такие два способа
// инициализации эквивалентны, в обоих просто вызывается конструктор
// Point(const Point&, const Point&).
Point radiusA = Point(pivotPoint, a);
Point radiusB(pivotPoint, b);
// Первое, что приходит в голову — посмотреть на полярные углы двух
// векторов из точек, и сравнить их. Полярный угол легко узнать как
// арктангенс отношения ординаты и абсциссы, для этого есть специальная
// функция atan2:
bool atan2Check = std::atan2(radiusA.y, radiusA.x) > std::atan2(radiusB.y, radiusB.x);
// Это будет работать, но не оптимально сразу по нескольким причинам.
// atan2 — довольно тяжёлая операция, внутри считаются какие-то ряды, в
// результате получается вещественное число с какой-то погрешностью,
// хотя у нас целочисленные координаты, и вполне возможно было бы
// сделать точное сравнение.
// Поэтому воспользуемся исключительно полезным свойством векторного
// произведения двух векторов из R2: его z-координата равна
// произведению длин векторов и синуса ориентированного угла между
// ними. Фактически то, что мы хотим проверить — положительность
// поворота от одного вектора к другому —, равносильна положительности
// этого синуса. Поэтому можно просто посчитать z-координату векторного
// произведения, и посмотреть не её знак.
bool crossProductCheck = (0 > radiusA.x * radiusB.y - radiusB.x * radiusA.y);
// Вообще-то должно получиться одно и то же.
assert(atan2Check == crossProductCheck);
return crossProductCheck;
}
Point pivotPoint;
};
int main() {
size_t n;
std::cin >> n;
std::vector<Point> points(n);
for (Point& point : points) {
std::cin >> point.x >> point.y;
}
// Найдём точку, минимальную сначала по x, затем по y:
// std::min_element — Стандартная функция, ищет минимальный элемент в
// полуинтервале между итераторами, возвращает итератор. Компаратор, как
// обычно, опционален.
std::vector<Point>::iterator minIter = std::min_element(
points.begin(), points.end(),
lexicographicalLess
);
// Переставим минимальный элемент в начало:
// Почти равносильно std::swap(points[0], *minIter)
// или std::swap(points[0], points[minIter - points.begin()])
std::iter_swap(points.begin(), minIter);
// Теперь хочется отсортировать остальные точки по полярному углу
// относительно точки points[0]. То есть точка A должна идти раньше точки
// B, если поворот от вектора из points[0] в A к вектору из points[0] в B
// совершался, скажем, против часовой стрелки.
// Если мы так сделаем, получится ломаная, удовлетворяющая требованиям.
//
// Получается, что для такого сравнения точек A и B компаратору нужно
// знать ещё и points[0], а компаратор это обычно функция, принимающая всего
// два аргумента. Что же делать?
//
// В этой задаче есть два способа справиться с проблемой:
//
// 1. Перед сортировкой перенести начало координат в точку points[0].
// В компараторе смотреть на поворот относительно начала координат.
// Вполне рабочее решение, кажется, не нуждающееся в комментарии.
//
// 2. Описать компаратор, представляющий из себя не функцию, а класс, в
// котором сохранена точка points[0], и который за счёт перегрузки оператора
// operator() можно вызывать как функцию. Его реализацию см. выше.
PositiveRotationChecker comparator(points[0]);
insertionSort(points.begin() + 1, points.end(), comparator);
// Готово, вы великолепны, можно выводить ответ:
for (const Point& point : points) {
std::cout << point.x << ' ' << point.y;
std::cout << '\n';
}
std::cout << '\n';
// Такой цикл (этот синтаксис называется range-based for) тоже устроен на
// итераторах, и без них бы не работал. Этот синтаксис преобразуется вот в
// такой обычный for:
for (
// Запоминаются две переменные: текущий итератор и итератор на конец
// контейнера.
// std::begin(points) — это то же самое, что points.begin(), то есть
// итератор на начало контейнера. Тем не менее, std::begin будет
// работать даже для статических массивов, у которых нет методов.
std::vector<Point>::iterator it = std::begin(points), end = std::end(points);
it != end;
++it
) {
const Point& point = *it;
// Далее тело range-based for'а:
std::cout << point.x << ' ' << point.y;
std::cout << '\n';
}
std::cout << '\n';
// Если вам нужно просто пробежаться по контейнеру, а номера позиций или
// итераторы не нужны, предпочтительно использовать range-based for.
}