FindThePerfectTriangle

TCO19 SRM 738 · 2018-09-29 · by wild_hamster

TCO19 SRM 738 · 2018-09-29 · by wild_hamster · Brute Force, Geometry

Show categories

Class Name: FindThePerfectTriangle

Return Type: int[]

Method Name: constructTriangle

Arg Types: (int, int)

Problem Statement

You are given the ints perimeter and area. Your task is to find a triangle with the following properties:

The coordinates of each vertex are integers between 0 and 3000, inclusive.
The perimeter of the triangle must be exactly perimeter, and its area must be exactly area.

If there are multiple solutions, you may choose any of them. Return a int[] with six elements: {x1, y1, x2, y2, x3, y3}, where (x1, y1), (x2, y2), and (x3, y3) are the coordinates of the vertices of your triangle. If there is no solution, return an empty int[] instead.

Constraints

area will be between 1 and 1,000,000, inclusive.
perimeter will be between 1 and 1000, inclusive.

Examples

6
11
Returns: { }

There are no valid triangles with area 6 and perimeter 11.

6
12
Returns: {1, 1, 1, 4, 5, 4 }

The example output describes a right triangle with vertices at (1, 1), (1, 4) and (5, 4). Its sides have lengths 3, 4, and 5, hence its perimeter is 12. The area of the triangle is (3*4)/2 = 6.

37128
882
Returns: {137, 137, 273, 410, 1, 410 }

72
64
Returns: {19, 19, 22, 23, 1, 43 }

126
108
Returns: {46, 46, 49, 50, 1, 70 }

34)

12
18
Returns: {1, 1, 4, 5, 1, 9 }

In this test case our solution constructed an isosceles triangle with vertices at (1, 1), (4, 5) and (1, 9).

Submissions are judged against all 179 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FindThePerfectTriangle with a public method vector<int> constructTriangle(int area, int perimeter) · 179 test cases · 2 s / 256 MB per case