TopCoder problem "FindTriangle" used in SRM 288 (Division I Level One , Division II Level Two)



Problem Statement

    

You are given the coordinates of several vertices in space. Each vertex is colored 'R', 'G' or 'B'. You are to determine the maximum possible area of a triangle such that all three of its vertices are the same color, or all three of its vertices are different colors.

You are given a String[] points describing the vertices. Each element of points will be in the form "color x y z", where color is 'R', 'G', or 'B', and x, y, z are integers with no leading zeroes.

 

Definition

    
Class:FindTriangle
Method:largestArea
Parameters:String[]
Returns:double
Method signature:double largestArea(String[] points)
(be sure your method is public)
    
 

Notes

-A triangle with all three vertices colinear, or two vertices overlapping, has area 0.
-Returned value must be within 1.0e-9 absolute or relative error.
 

Constraints

-points will have between 5 and 50 elements, inclusive.
-Each element of points will be formatted as "color x y z" (quotes added for clarity).
-Each color will be 'R', 'G', or 'B'.
-Each x, y and z will be an integer between 0 and 999, inclusive, with no leading zeros.
 

Examples

0)
    
{"R 0 0 0",
 "R 0 4 0",
 "R 0 0 3",
 "G 92 14 7",
 "G 12 16 8"}
Returns: 6.0
The coloring restrictions mean that we can only consider the first three points, which form a classic 3-4-5 triangle with an area of 6.
1)
    
{"R 0 0 0",
 "R 0 4 0",
 "R 0 0 3",
 "G 0 5 0",
 "B 0 0 12"}
Returns: 30.0
Our bet here is to take the red point at the origin, the green point, and the blue point. These actually form a 5-12-13 triangle. Area = 30.
2)
    
{"R 0 0 0",
 "R 0 4 0",
 "R 0 0 3",
 "R 90 0 3",
 "G 2 14 7",
 "G 2 18 7",
 "G 29 14 3",
 "B 12 16 8"}
Returns: 225.0
We have a lot more choices here.
3)
    
{"R 0 0 0",
 "R 1 1 0",
 "R 4 4 0",
 "G 10 10 10",
 "G 0 1 2"}

Returns: 0.0
All three red points are colinear.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5943

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9809&pm=5943

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Geometry, Math