ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1062. Триатлон

Counter example for 3D convex hull algorithm
Послано [MF] Radomir Djokovic 18 янв 2012 01:52
I think I found counter example for this, ie. set of points of which one is inside the 3D convex hull, but it's appropriate contenstant can win. If we are given for contestant with following speeds:

1 1 2
1 1 4
100 1 3
1 100 3
20 20 3

If we choose paths of length 100, 100, 3, than last contestant (20, 20, 3) can win with time 100/20 + 100/20 + 3/3 = 11. But, for this points 3D convex hull consists of (1, 1, 2), (1, 1, 4), (100, 1, 3) and (1, 100, 3).

Does anyone know if I'm wrong and why?
Re: Counter example for 3D convex hull algorithm
Послано Accepted 15 июл 2013 09:35
Consider that the sum of swim,bike and run is a const number,so we can let the total s=1,then we can solve it for 2D convex hull alogrithm rather than 3D.
Re: Counter example for 3D convex hull algorithm
Послано Chitanda Eru 4 сен 2013 04:34
You should use reciprocals of speeds (preferably multiplied by some constant) as coordinates, but not just the speeds. After applying such an "inversion" to the points in your example, the last one jumps out of the convex hull formed by others.