Добрый день!
Сейчас, прорешивая задачу http://codeforces.me/contest/257/problem/C, я получил сомнительный рантайм. Вот этот код получает Re1:
Получается, что функция atan2, вызываемая от одного и того же набора аргументов, может выдавать различные значения. Почему?!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Не знаю, не знаю. У меня такой код получил АС.
UPD: одна из ваших попыток до сих пор висит на первом тесте)
Еще раз, сортировка структур, как сортировка вида atan2(p1.y, p1.x) < atan2(p2.y, p2.x) падает на сервере по внутреннему рантайму, а если сначала запихнуть значения atan2 в некое поле структуры, то это получает AC. Проблема именно в том, что atan2 работает странно на сервере и выдает различные значения при одинаковых параметрах. У меня на компе все ок.
Ты похоже не понял о чем речь. Суть в том, что в коде есть такие 2 строчки
RE 1 Вылетает из-за того, что ps[i].value присваивается atan2 (ps[i].y, ps[i].x), но потом вызывается assert (ps[i].value, atan2 (ps[i].y, ps[i].x)), то есть 2 идентичных вызова atan2 дают разные значения. В этом-то и заключается вопрос : Почему?
Мирас, спасибо конечно, но я сам понял косяк. Все дело в точности. Вот посылка, получившая АС.
Ну потому что даблы плюс оптимизатор. Можно считать, что любая функция возвращает ans+e, где e — погрешность с матожиданием ноль.
Т.е. ничего точно посчитаться не может (кроме, возможно, целых/полуцелых, которые хранятся точно). Вообще, жизнь так устроена :)
UPD: продолжение истории.
То есть, все функции такие. Ок, понял, спасибо.)
Я неожиданно осознал, что эта проблема снова вернулась ко мне. Еще раз, как мне писать сортировку по углам, чтобы такой проблемы не существовало? http://codeforces.me/contest/257/submission/3207519 Предположим, я могу не ставить лишних ассертов. Но сортировка и сама прекрасно падает.
вроде, это можно делать векторным и скалярным произведением в целых числах
А если координаты точек в даблах?
atan2, если различие больше 0.1, то векторное произведение. Если нет точек около нуля, то оно существенно отличается от нуля.
А векторное произведение не будет также падать внутри sort?
А да, действительно будут такие же проблемы с точностью. Это хорошо работает когда точки целые, но по кругу.
Если целые, то я по-другому делаю. Я делю все вокруг на четыре части: 1) y = 0, x > 0 2) y > 0 3) y = 0, x < 0 4) y < 0 От точки есть функция type(). Сравниваю сначала ее, потом векторное. Но интересно про даблы.
В VC++ результат тот же.
Я подозреваю, что это связано с тем, что у процессоров архитектуры x86/x64 внутренняя разрядность вещественных регистров 80 бит. В то время как разрядность дабла 64 бита. Тоесть сохраняя результат вычисления мы теряем 16 бит. Наверняка у тебя в assert сравнивается сохранённое 64 битное значение с только что полученным 80 битным и последнее более точное.
Попробуй эксперимент:
А почему std::sort тогда падает?
Я подозреваю что atan(x) < atan(x) первый раз запишет атан в память и обрежет, а второй возьмёт из регистра. В результате первый получиться меньше второго, что вернёт тру, что нарушит целостность сорта.
Используй только сохранённые значения. Зачем тебе тангенс прямо в предикате считать?
Да, круто, понял.
Чтобы память лишнюю не использовать. Здесь я так и сделал.
На самом деле, меня больше волнует, можно ли писать компаратор: "векторное произведение < 0". Ведь легко может оказаться, что a < a. Значит, сорт опять упадет по рантайму. А это совсем не то, о чем хочется думать на контесте. Писать "... < -EPS"? Но тогда придется выбирать EPS, а какой, не ясно.
Да и на месте векторного произведения может оказаться все что угодно. Что делать?)
"Векторное произведение < 0" в вещественных числах писать, конечно, нельзя
Почему не понятно, какой eps? Если сравниваем углы, то "минимальное значение угла" / 2. Если сравниваем векторные произведения, то нужно нормировать вектора и опять же получаем "минимальное значение угла" / 2 (sin(a) ~= a).
Если углы посчитаны точно, получаем eps = 10 - 18 (long double). Что отлично работает, если координаты исходных векторов до 109 (минимальный угол как раз чуть больше 10 - 18).