Здравствуйте!
Пытался сегодня научиться писать алгоритм построения выпуклой оболочки, но что-то пошло не так :( Можете, пожалуйста, помочь найти баг в http://ideone.com/IXFfS9 ?
Вроде всё выглядит просто, но продолжаю получать упертый ВА4 в задаче А http://codeforces.me/gym/100173
Даже не могу придумать тест, который завалит моё решение.
Заранее спасибо за помощь!
Перед сортировкой надо из координат каждой точки вычесть координаты самой_нижней_а_из_них_самой_левой_точки. Сам тоже на этом попадался, дооолго багу искал :)
Ну так вычитаю же -- в строках 54 и 55.
А, все вижу. Когда увидел что перед сортировкой не вычитал, вспомнил, что получил WA4 по этой задаче из-за того что не смещал точки, подумал что у тебя по той же причине.
Я бы посоветовал вычитать не каждый раз, когда сравниваем, а лишь один раз перед сортировкой. Но это не обязательно
Никогда не используй atan2, когда можешь обойтись векторным произведением. Считай все в целых числах. Если никак, то считай в дробных, но старайся не использовать тригонометрические функции. Они довольно неточные.
Вот мой код с AC, можешь глянуть: http://pastebin.com/4kdwu7A9
UPD. Еще раз посмотрел код, вещественные числа сравнивают так:
abs(a - b) < EPS
Спасибо за ответ!
Можно, пожалуйста, подробней про векторное произведение? Ну, или ссылку на почитать. С atan'ами все более-менее понятно, а здесь как-то не очень ясно, как всё работает.
Какое значение эпсилонов оптимально выбирать для float, double, long double?
P.S.: твой код даёт WA19 на той задаче.
Ну, тут много объяснять, лучше просто почитать. Еще его косым называют
Обычно берут 1e-9 (или 1e-6, когда вычисления не очень точные). А вообще, зачем вообще float использовать? В олимпиадах обычно всегда лучше double
Странно, что WA19, щас зашлю на CF и гляну код..
P.S. Я решал эту задачу с другого сайта, а там были другие ограничения
UPD. Увидел, что AC
UPD2. В процессе засылания тоже встретился тест 19, увидел, что причиной тому переполнение было, надо было в long long считать, тогда все заходило :)
Всё ясно, спасибо!
Строчка 98. Точно
i <= N
? Может там<
?Вывод на тесте:
не порадовал. Кстати, изменение
<=
на<
помогло.Меня больше всего не порадовало непосредственное сравнение:
I dont get what do you do in cmp() exactly, but might be a mistake in line 54:
this might be true
instead of
Справился, всем большое спасибо за помощь!