SRM 738, D1, 250-Pointer (FindThePerfectTriangle)

James S. Plank

Tue Oct 9 15:18:25 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
confirm.cpp -- A program that will confirm whether a triangle is correct for the given area and perimeter.
grader.sh -- A shell script to grade your program.
randinput.txt -- 100 random inputs. Half of them have valid triangles, and half of them do not.
Problem Given in Topcoder: September, 2018
Competitors who opened the problem: 148
Competitors who submitted a solution: 123
Number of correct solutions: 57
Accuracy (percentage correct vs those who opened): 38.5%
Average Correct Time: 27 minutes, 54 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given two integers, which represent the perimeter and area of a triangle.
Your job is to return the coordinates of a triangle that has integer coordinates, and whose perimeter and area are the given perimeter and area.
Return the coordinates as a vector. If the three points of the triangle are (x₁,y₁), (x₂,y₂) and (x₃,y₃),, then you should return the vector { x₁, y₁, x₂, y₂, x₃, y₃ }.
If there is no such triangle, then return an empty vector.
If there are multiple triangles that work, return any one of them.
The area will between 1 and 1,000,000, and the perimeter will be between 1 and 1,000.
Your coordinates must be between 0 and 3,000.

The examples

#        area    perimeter      answer
-    --------    ---------      -------------------------------
0           6           11      { }
1           6           12      { 1, 1, 1, 4, 5, 4 }
2       37128          882      { 137, 137, 273, 410, 1, 410 }
3          12           18      { 1, 1, 4, 5, 1, 9 }
4       18096          928      { 1, 1, 1, 88, 417, 88 }
5     1000000         1000      { }

Testing yourself

This is a hard one to test, but here's what I have. I have 100 input values in randinput.txt. As you can see, each pair of input values is followed by "yes" or "no". If "no", then there's no valid answer for this area and perimeter. If "yes", then there is a valid answer.

There is a program here called confirm.cpp. Compile it with:

UNIX> g++ -o confirm confirm.cpp

You give it 8 inputs -- area, perimeter, and the three points. If the three points make a valid triangle for the area and perimeter, it will print "Good". Otherwise, it will print some error message.

So:

UNIX> echo 6 12 1 1 1 4 5 4 | ./confirm
Good
UNIX> echo 6 11 1 1 1 4 5 4 | ./confirm
Perimeters don't match
UNIX>

Compile your program using main.cpp into a.out. Then run the shell script grader.sh. You should see it print one test per line, and it will print "ok" if you pass each test.

Hints

As always with Topcoder, we are confronted with a decision of whether to be smart, or whether to take a simplistic approach and see if it completes in time. As usual, the second approach seems to work better.

The simplistic approach is to enumerate. However, you cannot enumerate triangle points, even those that include the origin, because there are way too many of those. It's better to try to enumerate sides of the triangle. The reason is that the sides have to have integer endpoints and integer lengths. Any fractional lengths will be irrational numbers, and cannot sum to an integer perimeters. So, let's try to enumerate all potential sides of the triangles.

What I did was enumerate all potential (x,y) pairs, and for each of these, I determined whether the line from (0,0) to (x,y) had an integer length. I did this for x and y up to 3000.

For a value of x and y, suppose I found that the line has an integer length. Then I store the x and y values in a vector associated with the length. Here are the vectors for lengths from 1 to 29:

length     (x,y) pts such that (0,0)-(x,y) has length
------     ------------------------------------------
 1         (0,1) (1,0)
 2         (0,2) (2,0)
 3         (0,3) (3,0)
 4         (0,4) (4,0)
 5         (0,5) (3,4) (4,3) (5,0)
 6         (0,6) (6,0)
 7         (0,7) (7,0)
 8         (0,8) (8,0)
 9         (0,9) (9,0)
10         (0,10) (6,8) (8,6) (10,0)
11         (0,11) (11,0)
12         (0,12) (12,0)
13         (0,13) (5,12) (12,5) (13,0)
14         (0,14) (14,0)
15         (0,15) (9,12) (12,9) (15,0)
16         (0,16) (16,0)
17         (0,17) (8,15) (15,8) (17,0)
18         (0,18) (18,0)
19         (0,19) (19,0)
20         (0,20) (12,16) (16,12) (20,0)
21         (0,21) (21,0)
22         (0,22) (22,0)
23         (0,23) (23,0)
24         (0,24) (24,0)
25         (0,25) (7,24) (15,20) (20,15) (24,7) (25,0)
26         (0,26) (10,24) (24,10) (26,0)
27         (0,27) (27,0)
28         (0,28) (28,0)
29         (0,29) (20,21) (21,20) (29,0)

There are 3370 such lengths, and the most values of (x,y) that a length has is 28. These numbers allow us to do a tractable enumeration.

Using the Triangle Inequality

The Triangle Inequality helps us with the enumeration. The Triangle Inequality states that if we sort the lengths of a triangle's sides to be a ≤ b ≤ c, then we know that b ≤ c < a + b. That allows us to enumerate as follows (p is the perimeter):

Enumerate all possible sides a ≤ p/3 .
Enumerate all possible sides b ≥ a ≤ p/3.
Calculate side c = p - a - b.
If c ≥ b, and a, b and c are ok according to the triangle inequality, then this is a potential answer. Call Is_Triangle_OK(a, b, c).
Otherwise, keep enumerating.

Here are the potential triangles for examples 0, 1 and 4, where the perimeters equal 11, 12 and 18. You'll note that we might not be able to construct triangles with these lengths and integer coordinates; however these are lengths that fit the triangle inequality and have the given perimeter.

Example 0

Is_Triangle_OK(1, 5, 5)
Is_Triangle_OK(2, 4, 5)
Is_Triangle_OK(3, 3, 5)
Is_Triangle_OK(3, 4, 4)

Example 1

Is_Triangle_OK(2, 5, 5)
Is_Triangle_OK(3, 4, 5)
Is_Triangle_OK(4, 4, 4)

Example 2

Is_Triangle_OK(2, 8, 8)
Is_Triangle_OK(3, 7, 8)
Is_Triangle_OK(4, 6, 8)
Is_Triangle_OK(4, 7, 7)
Is_Triangle_OK(5, 5, 8)
Is_Triangle_OK(5, 6, 7)
Is_Triangle_OK(6, 6, 6)

Time to write Is_Triangle_OK(a, b, c). This has two parts:

Does the area of this triangle equal the given area?
Can you make the triangle with integer coordinates?

Let's answer the first question. I'm not sure how well-known Heron's Formula is, but when I googled "Calculating the area of a triangle from the length of all three sides", I was directed to https://www.mathopenref.com/heronsformula.html, which tells me that the area is:

sqrt( q (q-a)(q-b)(q-c) )

Where q is the perimeter over two. Who knew? Well, now I know. And you know. And that's an easy calculation. The area is only going to be an integer, btw, if q is an integer, so the perimeter has to be a multiple of two. Given that, it's best to simply calculate the square of the area to see if it equals the square of the given area. That way, you avoid floating point issues.

So, go ahead and write that code. That's the first test of your Is_Triangle_OK(a, b, c).

Your last task is to find coordinates if you have a valid (a, b, c). To do that, what I did was another enumeration:

Enumerate all possible (x,y) values for c. Set the first two points of your triangle to (0,0) and (x,y).
Now, enumerate all possible (x',y') values for a. Set the third point of your triangle to (x',y').
From these three points, you can calculate the length for the b side. If it equals b, then you've got an answer! Convert those triangle points to points that are ≥ 0, and you're done. (BTW, best to calculate the square of the length and compare to the square of b).
You should try again with (x',-y'). Just saying.

An example, please?

Let's do example 1, where the perimeter is 12 and the area is 6. As I said above, the Is_Triangle_OK calls are:

Is_Triangle_OK(2, 5, 5)
Is_Triangle_OK(3, 4, 5)
Is_Triangle_OK(4, 4, 4)

Checking the areas, you'll see that only the (3, 4, 5) combination has an area of 12. Let's look at the (x,y) values for lengths 3, 4 and 5 (from above):

 3         (0,3) (3,0)
 4         (0,4) (4,0)
 5         (0,5) (3,4) (4,3) (5,0)

So, we'll start looking at all of the potential points where c = 5 and a = 3:

Triangle Points	Square of the b side.
(0,0) (0,5) (0,3)	4
(0,0) (0,5) (0,-3)	64
(0,0) (0,5) (3,0)	34
(0,0) (3,4) (0,3)	10
(0,0) (3,4) (0,-3)	58
(0,0) (3,4) (3,0)	16
(0,0) (4,3) (0,3)	16
(0,0) (4,3) (0,-3)	52
(0,0) (4,3) (3,0)	10
(0,0) (5,0) (0,3)	34
(0,0) (5,0) (0,-3)	34
(0,0) (5,0) (3,0)	4

As you can see, when the triangle is (0,0) (3,4) (3,0), the square of the b side is 4², so we have our answer!