Здравствуйте, Аноним, Вы писали:
Похоже, что проблема тут не с алгоритмом сортировки, а с пониманием условия по которому нужно сортировать. А сам алгоритм можно выбрать практически любой.
А>и как можете заметить внутри каждого среза с одним Уi
А>относительно Хо, на примере первого среза из
А>первого варианта:
А>А><---
А>2 1
--->>
А> 3
А>
А>сперва две точки по убыванию икса, относительно Хо,
А>потом третья — идущая по возрастанию...
А>точка 1 принадлежит Хо, точка 3 строго больше.
Очень плохое описание. Мне кажется, что оно противоречит примерам.
А>вопрос — как сие сделать на С++???
std::sort же.
Использовать так:
std::vector<Points> points;
...
std::sort(points.begin(), points.end(), cmp(x0));
Описав вначале предикат сравнения:
struct cmp {
cmp(int X0): x0(X0) {}
bool operator()(const Point& a, const Point& b) const {
if (a.y != b.y)
return a.y < b.y; // точки всегда упорядочены по ординатам
if (a.x <= x0 && b.x <= x0)
return a.x > b.x; // точки слева от прямой x=x0 упорядочены в по убыванию абсцисс
else
return a.x < b.x; // точки из правой полуплоскости и из разных полуплоскостей упорядочены по возрастанию абсцисс
}
int x0;
};
Соответственно, второй случай, с инвертированием оси Y, делается заменой одного символа в кода, ну или добавлением параметра, если так тебе будет удобнее.
