一点が三角に入っている事を試す

最近トップコーダーのアルゴリズム問題に苦しんでいます。Given a set of vertices, one was required to compute the number of triangles constructed from those vertices which contain the origin. While enumerating the triangles is a trivial triple-for loop with (n choose 3) complexity for n vertices, testing whether a given triangle contains the origin is not. The author finally found a method whereby the origin is inside a triangle if rays from each vertex to the opposite side can pass through the origin and fall within the side. This problem is solved by deducing the equations of the sides and lines from vertices to the origin in point-slope form. The problem is further complicated by the use of double-precision floating point numbers (sign mantissa exponent). One problem is that debug prints may use inadequate precision to illustrate differences at lower decimal places. Another problem is that decimal values read into memory from input, if they differ at the 16th decimal position, may have the identical 64-bit floating point representation, as the formula is
decimal = (-1)^s*1.b1b2..b52*2^(e1e2...e11), where s is the sign bit, bi are the significand bits, and ei are the exponent bits.