Блог пользователя ScienceGuy

Автор ScienceGuy, история, 6 лет назад, По-английски

I am trying to sort vector of points (pairs of integers) by the polar angle in counter-clockwise order around the first entry of the vector. I get wrong output, but can't find the problem in the code. I will appreciate it if you point out what I'm doing wrong. Here is my code: https://pastebin.com/mn6jZgyF

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 9   Проголосовать: нравится +3 Проголосовать: не нравится

В вашем случае в 9-10 строчках следует написать:

long long orient = (lPoint.second-p0.second)*(rPoint.first-p0.first) -
                            (lPoint.first-p0.first)*(rPoint.second-p0.second);

Но обычно пишут свою геометрию (чем проще написано, тем проще дебажить), например, я написал бы так:

struct pt {
    double x, y;
};

pt get(pt a, pt b) { // получаем вектор по двум точкам
    return pt(b.x-a.x, b.y-a.y);
}

ld cross(pt a, pt b) { // cross product
    return a.x*b.y - a.y*b.x;
}

bool cmp(pt a, pt b) {
    if (a == p0) {
        return 1;
    }
    if (b == p0) {
        return 0;
    }
    pt oa = get(p0, a);
    pt ob = get(p0, b);
    return cross(oa, ob) < 0;
}
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кажется, что такая cmp функция не транзитивна, нет?

    И еще -- это cross product, а не dot product.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо за ответ!
      Вынужден согласиться со вторым замечанием (fixed)
      Про транзитивность могу сказать следущее — я эту функцию скопировал из сабмита который зашел, так что, если Вы правы, то, наверное, тесты слабые)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The comparison function has to be a strict weak ordering. Yours isn't. You keep the point at index 0 in the array you are sorting, and according to your comparison function this point is equivalent ("equal") to any other point because the cross product is always zero.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Use this compare:


comp(a,b) { if(quarter(a)==quarter(b)) return cross(a,b)>0;//or cross(a,b)<0 else return quarter(a)<quarter(b); }