ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1062. Triathlon

Counter example for 3D convex hull algorithm
Posted by [MF] Radomir Djokovic 18 Jan 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
Posted by Accepted 15 Jul 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
Posted by Chitanda Eru 4 Sep 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.