Connection Status:
Competition Arena > BestTriangulation

BestTriangulation

SRM 278 · 2005-12-19 · by Vedensky

SRM 278 · 2005-12-19 · by Vedensky · Brute Force, Geometry
Class Name: BestTriangulation
Return Type: double
Method Name: maxArea
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You have a convex polygon. You select three consecutive vertices and create a triangle with them. Remove this triangle from the polygon (if you had a polygon with N vertices, the resulting polygon would have N-1 vertices). Repeat this process until the remaining polygon is a triangle.

You are given a String[] vertices, representing the vertices of the polygon in clockwise order. Each element will be formatted as "X Y", where X and Y are the coordinates of a vertex. Return a double representing the area of the largest possible triangle that can remain at the end.

Notes

  • The returned value must be accurate to 1e-9 relative or absolute.

Constraints

  • vertices will contain between 3 and 35 elements, inclusive.
  • Each element of vertices will be formatted as "X Y", where X and Y are integers without leading zeroes.
  • Each X and Y will be between 1 and 10000, inclusive.
Examples
0)
{"1 1", "2 3", "3 2"}
Returns: 1.5

The polygon is already a triangle, so you cannot perform any cuts.

1)
{"1 1", "1 2", "3 3", "2 1"}
Returns: 1.5

Here you must perform one cut. If you cut vertices (3, 0, 1), a triangle of area 1.5 will remain. If you cut vertices (0, 1, 2), a triangle of area 1 will remain. If you cut vertices (1, 2, 3), a triangle of area 0.5 will remain. If you cut vertices (2, 3, 0), a triangle of area 1 will remain. Your best option is to cut (3, 0, 1).

2)
{"1 2", "1 3", "2 4", "3 4", "4 3", "4 2", "3 1", "2 1"}
Returns: 3.0

In such an 8-gon, you must cut the following triangles in order: (7, 0, 1), (7, 1, 2), (2, 3, 4), (4, 5, 6), (4, 6, 7). Finally, a triangle with vertices (2, 4, 7) is left, and its area is 3.

3)
{"6 2", "2 1", "1 2", "1 4", "2 6", "5 6", "6 5"}
Returns: 10.0
4)
{"1 1", "1 2", "10000 10000"}
Returns: 4999.5

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

Coding Area

Language: C++17 · define a public class BestTriangulation with a public method double maxArea(vector<string> vertices) · 96 test cases · 2 s / 256 MB per case

Submitting as anonymous