FindTriangle
SRM 288 · 2006-02-08 · by Olexiy
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
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.
{"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.
{"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.
{"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.
{"R 0 0 0",
"R 0 4 0",
"R 0 0 3",
"R 26 71 3",
"R 27 72 3",
"R 28 73 3",
"R 29 74 3",
"R 30 75 3",
"R 31 76 3",
"R 32 77 3",
"R 33 78 3",
"R 34 79 3",
"R 35 80 3",
"R 36 81 3",
"R 37 82 3",
"R 38 83 3",
"R 39 84 3",
"R 40 85 3",
"R 41 86 3",
"R 42 87 3",
"R 43 88 3",
"R 44 89 3",
"R 45 90 3",
"R 46 91 3",
"R 47 92 3",
"R 48 93 3",
"R 49 94 3",
"R 50 95 3",
"R 51 96 3",
"R 52 97 3",
"R 53 98 3",
"R 54 99 3",
"R 55 1 3",
"R 56 2 3",
"R 57 3 3",
"R 58 4 3",
"R 59 5 3",
"R 62 6 3",
"R 63 7 3",
"R 64 8 3",
"R 65 9 3",
"R 66 10 3",
"R 67 11 3",
"R 68 12 3",
"R 87 13 3",
"R 88 14 3",
"R 89 15 3",
"R 88 16 3",
"R 93 17 3",
"R 90 18 3"}
Returns: 4146.737452504077
{"R 0 0 20",
"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 19 41 3",
"B 12 16 8"}
Returns: 1317.245990694221
{"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.
{"R 0 0 0",
"R 0 49 17",
"R 0 98 34",
"R 0 10 10",
"G 100 100 100"}
Returns: 320.0
Notice here that our first three red points are colinear.
Submissions are judged against all 62 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FindTriangle with a public method double largestArea(vector<string> points) · 62 test cases · 2 s / 256 MB per case