| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
Добрый день!
Сейчас, прорешивая задачу http://codeforces.me/contest/257/problem/C, я получил сомнительный рантайм. Вот этот код получает Re1:
Получается, что функция atan2, вызываемая от одного и того же набора аргументов, может выдавать различные значения. Почему?!
Не знаю, не знаю. У меня такой код получил АС.
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).