#include <bits/stdc++.h> using namespace std; struct point /// структура обозначающая точку в нашей системе координат { int x, y; }; point fst; /// 1 - я точка long long dist_sq(int x1 , int y1 , int x2 , int y2) { /// функция, которая возвращает квадрат расстояние от 1-й точки до другой long long X1 = x1 , X2 = x2 , Y1 = y1 , Y2 = y2; return ((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2)); } long long cross (point a1, point a2, point b1, point b2) /// функция, которая возвращает косое произведение векторов { return 1ll * (a2.x - a1.x) * (b2.y - b1.y) - 1ll * (b2.x - b1.x) * (a2.y - a1.y); } bool comporator(point l , point r) { /// компоратор для сравнения значений косого произведения в sort if (cross(l , fst , fst , r) < 0) { return 1; } if (cross(l , fst , fst , r) == 0 && dist_sq(fst.x , fst.y , l.x , l.y) < dist_sq(fst.x , fst.y , r.x , r.y)) { return 1; } return 0; } int main() { int n; cin >> n; point a[n]; for (int i = 0; i < n; i++) { /// считывание + нахождение самой левой точки из самых нижних cin >> a[i].x >> a[i].y; if (a[0].y > a[i].y) { swap(a[0] , a[i]); } else { if (a[0].y == a[i].y && a[i].x < a[0].x) { swap(a[0] , a[i]); } } } fst = a[0]; /// самая первая точка sort(a + 1 , a + n , comporator); /// сортировка(от второй точки) deque <point> st; /// стек для построения оболочки st.push_back(a[0]); for (int i = 1; i < n; i++) /// проход по алгоритму построения { while (st.size() > 1 && cross(st[st.size() - 2] , st[st.size() - 1] , st[st.size() - 1] , a[i]) <= 0) { st.pop_back(); } if (st.back().x != a[i].x || st.back().y != a[i].y) st.push_back(a[i]); } if (n % 2 != 0) { /// т.к. в 1877 если n нечетно нужно вывести оболочку по часовой стрелке, то развернём стек reverse(st.begin() , st.end()); } cout << st.size() << endl; for (auto to : st) { /// вывод оболочки cout << to.x << " " << to.y << endl; } return 0; }
1
Выпуклая оболочка Грехэма (сортировка по косому произведению)
Автор LVP, 24 окт 2020 11:57
В этой теме нет ответов
#1
Отправлено 24 октября 2020 - 11:57
Код от Кузьмичева Алексея, нахождения выпуклой оболочки по Алгоритму Грехема , используя сортировку точек по Углу через косое произведение векторов (решение задачи Informatics/mccme.ru 1877)
- studybayws, Sdvilledups, Anaerorom и 16 другим это нравится
- Нравится
Виктория Павловна
Количество пользователей, читающих эту тему: 1
0 пользователей, 1 гостей, 0 анононимных