Discussion @ 1062. Triathlon @ Timus Online Judge

Use algebra, neither simplex method nor 3d convex hull hedrok 7 Apr 2008 21:40

My solution runs only 0.015 (http://acm.timus.ru/status.aspx?space=1&num=1062&author=34678) and is based on simple algebra only.
Maybe 3d convex hull is faster, but it is much more complex to implement.
So i think Huang Yizheng is right. My solution isn't greedy at all and i think it's right.

Re: Use algebra, neither simplex method nor 3d convex hull svr 7 Apr 2008 22:33

But 3-d convex hull realization may be taken somewhere
acide and it is good practice. For me it was taken 5 min to
understand that 3-d convex hool could be applied and it is
well to context. But difficult to find accurate with
hight precision effective realisation but after having it
3-d convex hool more better.

Edited by author 07.04.2008 22:34

Re: Use algebra, neither simplex method nor 3d convex hull hedrok 9 Apr 2008 00:25

Could you give me good link?
You see, i haven't implemented it because everything i found seemed very time-consuming to write. I'm preparing to olympiad, so i look for algos which i can implement fast without mistakes.

Re: Use algebra, neither simplex method nor 3d convex hull Denis Koshman 21 Aug 2008 04:33

As for this problem O(N^3) is ok. One of easy ways is to pick every pair of points and rotate a plane around them through others to get all of them on one side.

Discussion of Problem 1062. Triathlon