Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » NEERC 2000 Triathlon
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Добрый день.
Забавная задача, предлагавшаяся на 1/2 финала в Питере (http://acmicpc-live-archive.uva.es/nuev … php?p=2218).
Есть подозрения, что решение связано с теорией ЛП.
Если у кого-то есть соображения -- поделитесь, пожалуйста.
Спасибо.
Только что получилось сдать на тимусе без всяких симплексов и конвекс холов.
Для каждого человека у нас есть N - 1 уравнений length1 * x + length2 * y + length3 * z < 0
взяв length3 за 1, получаем N - 1 полуплоскостей.
каждая из точек пересечения полуплоскостей дает нам возможный length1 и length2
Получилось O(N^4) но на практике работает быстро.
Может кто пояснить length1 * x + length2 * y + length3 * y < 0 почему length3*y ?? если я правильно понял x(y,z?) - Это (Vn-V)/(V*Vn) - где Vn скорость участника на 1-м (2, 3-м) участке, а V - это скорость потенциального победителя
так вот вопрос почему length3 - можно взять за 1-цу!
Решаем систему линейных неравенств вида а * x + b * y + c * z < 0 (*), где a, b, c -- коэффициенты; x, y, z - неизвестные, причем x, y, z > 0. Можем разделить все на z и получить систему из двух неизвестных. Можно поступить иначе. Пусть (x, y, z) - решение. Тогда x + y + z = k => x' + y' + z' = 1 (**), где x' = x / k, y' = y / k, z' = z / k. Выражая из (**) z' и подставляя в (*) получаем также систему с двумя неизвестными.
Спасибо.
Да. Всё оказалось достаточно просто. Только отладка заняла много времени. 
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » NEERC 2000 Triathlon