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

Problems with standard 2D convex hull
Автор 1k_trash, 11 лет назад, По-русски

Здравствуйте!

Пытался сегодня научиться писать алгоритм построения выпуклой оболочки, но что-то пошло не так :( Можете, пожалуйста, помочь найти баг в http://ideone.com/IXFfS9 ?

Вроде всё выглядит просто, но продолжаю получать упертый ВА4 в задаче А http://mirror.codeforces.com/gym/100173

Даже не могу придумать тест, который завалит моё решение.

Заранее спасибо за помощь!

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

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

Перед сортировкой надо из координат каждой точки вычесть координаты самой_нижней_а_из_них_самой_левой_точки. Сам тоже на этом попадался, дооолго багу искал :)

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну так вычитаю же -- в строках 54 и 55.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      А, все вижу. Когда увидел что перед сортировкой не вычитал, вспомнил, что получил WA4 по этой задаче из-за того что не смещал точки, подумал что у тебя по той же причине.

      1. Я бы посоветовал вычитать не каждый раз, когда сравниваем, а лишь один раз перед сортировкой. Но это не обязательно

      2. Никогда не используй atan2, когда можешь обойтись векторным произведением. Считай все в целых числах. Если никак, то считай в дробных, но старайся не использовать тригонометрические функции. Они довольно неточные.

      Вот мой код с AC, можешь глянуть: http://pastebin.com/4kdwu7A9

      UPD. Еще раз посмотрел код, вещественные числа сравнивают так: abs(a - b) < EPS

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Спасибо за ответ!

        1. Можно, пожалуйста, подробней про векторное произведение? Ну, или ссылку на почитать. С atan'ами все более-менее понятно, а здесь как-то не очень ясно, как всё работает.

        2. Какое значение эпсилонов оптимально выбирать для float, double, long double?

        P.S.: твой код даёт WA19 на той задаче.

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

          1. Ну, тут много объяснять, лучше просто почитать. Еще его косым называют

          2. Обычно берут 1e-9 (или 1e-6, когда вычисления не очень точные). А вообще, зачем вообще float использовать? В олимпиадах обычно всегда лучше double

          3. Странно, что WA19, щас зашлю на CF и гляну код..

          P.S. Я решал эту задачу с другого сайта, а там были другие ограничения

          UPD. Увидел, что AC

          UPD2. В процессе засылания тоже встретился тест 19, увидел, что причиной тому переполнение было, надо было в long long считать, тогда все заходило :)

          → Ответить
»
11 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Строчка 98. Точно i <= N? Может там <?

Вывод на тесте:

3
-2 -1
-1 0
-2 0

не порадовал. Кстати, изменение <= на < помогло.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Меня больше всего не порадовало непосредственное сравнение:

        float angle1 = atan2(deltaY1, deltaX1);
    float angle2 = atan2(deltaY2, deltaX2);
 
    if(angle1 < 0.0) angle1 += 2.0 * PI;
    if(angle2 < 0.0) angle2 += 2.0 * PI;
 
    if(angle1 == angle2)
        ...
    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I dont get what do you do in cmp() exactly, but might be a mistake in line 54:

this might be true 

float deltaX1 = p1.x - P.x, deltaX2 = p2.x - P.x;

instead of 

float deltaX1 = p1.x - P.y, deltaX2 = p2.x - P.x;
→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Справился, всем большое спасибо за помощь!

→ Ответить