Перейти к содержимому


Выпуклая оболочка Грехэма (сортировка по косому произведению)


В этой теме нет ответов

#1 LVP

    Продвинутый пользователь

  • Администраторы
  • 187 сообщений
  • ГородВитебск

Отправлено 24 октября 2020 - 11:57

Код от Кузьмичева Алексея, нахождения выпуклой оболочки по Алгоритму Грехема , используя сортировку точек по Углу через косое произведение векторов (решение задачи Informatics/mccme.ru 1877)

#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

0 пользователей, 1 гостей, 0 анононимных