My solution is based on the next idea. When we check the current contestant we should know if there exists such vector x = (x0, x1, x2) that for every i = 1..n - 1 scalr product (v_i,x) > 0. I use simplex-method to solve this problem with such inequalities:
(v_0, x) >= EPS
(v_1, x) >= EPS
...
(v_n-1, x) >= EPS
x0 >= EPS
x1 >= EPS
x2 >= EPS
x0 + x1 + x2 <= 1500

BUT I HAVE TLE on test 21. I couldn't improve my simplex-method implementation.
Any who solved this problem using algebra, please, give me some hints. Thank you.

Try to suppose that x0=1

Edited by author 21.09.2007 23:35

Oh, yeah!!! I've got ACCEPTED. Thank you Razdolbay from SIS. You've really helped me.

Classic idea: 3d convex hull.
Points inside- No,on the boundary -Yes.
But implementation of effective 3d convex hull
is'n easy. Having it done we will have effective
voronoi diagrams and plenty of difficult timus problems
admissible.

Edited by author 09.10.2007 16:11

Additional!
Simplex method is O(exp(n)) for bad tests.
3d convex hull is O(n*log(n)) in wast case.

A got Ac 0.015 using convex hull but and it is
important, in D2 and when body defined as halpfspaces intersection. Simply we may consider a:=a/(a+b+c),
b:=b/(a+b+c),c:=c/(a+b+c) where a,b,c- length of
distances and after use c=1-a-b projecting by the
such way the problem from D3 to D2.

Edited by author 31.12.2008 15:14

How to implement 3d convex hull in O(n*log(n))?
The best idea, which I know is O(n^2)...

In simple method errors are added and therefore
difficult to use comparing with EPS.
On this problem(I have Ac 0.015 using convex hull in D2)
I fistly understood that combinatorial methods(intersection line and polygone) have big advanteges before
simplex. I used simplex method above BigInteger/BigInteger
in java- righly but very slow,simplex above double- impossible to make choice of EPS and got Ac from the
first attempt using combinatorial approach.

Why, using transformation of coordinates specified in a post svr, and doing the projection specified in the same place, we receive an equivalent problem? Points pass to external surfaces D3 of set in points at external edges D2 of projective set - is it right?

Edited by author 24.10.2009 04:03

Of course. I am on line all times. That I said is true
 but much time is gone. I am Liability on my posts and soon  you will have most detailed isue, wait some time,
please.

Edited by author 24.10.2009 19:59

I hope, I trust and I wait.

Answer.
This morning I have drinked cofee an remember.
1) h1/ai+h2/bi+h3/ci<h1/aj+h2/bj+h3/cj ~
h1*ai1+h2*bi1+h3*ci1<h1/aj1+h2/bj1+h3/cj1
where ai1=1/ai,bi1=1/bi,ci1=1/ci,aj1=1/aj,
bj1=1/bj,cj1=1/cj. So first convertion is a:=1/a,b:=1/b,c:=1/c
2) h1*ai+h2*bi+h3*ci<h1/aj+h2/bj+h3/cj for all j
is ~ to
(ai-aj)*h1+(bi-bj)*h2+(ci-cj)*h4<0 for all j
or Aj*h1+Bj*h1+Cj*h3<0.
3) Let Q=Aj+Bj+Cj(In my solution i accepted that Q!=0
if no then Cj=-Aj-Bj and so on.)
Let Aj=Aj/Q;Bj=Bj/Q;Cj=Cj/Q.
We  have Aj*h1+Bj*h2+Cj*h3<0 or >0 and Aj+Bj+Cj=1.
4) ~ (Aj-Cj)*(h1-h3)+(Bj-Cj)*(h3-h3)< -Cj;
5) Let Qj=Aj-Cj;Sj=Bj-Cl;Rj=-Cj
h1-h3=x1;x2=h2-h3
We have that D2 point (x1,x2) belong to internity of
convex body satisfying system of   inequalities
Qj*x1+Sj*x2<Rj or >Rj. This is simmple D2 theory.

Edited by author 27.10.2009 08:09

Edited by author 01.01.2010 15:46

Whether probably to write qhull algorithm for space of arbitrary dimension? How much it is difficult?

Edited by author 05.01.2010 03:10

I have an quick hull algorithm implementation for an arbitrary dimensional space. Can you provide a list of the problems, which is suitable for application of the convex hull algorithm?