Connection Status:
Competition Arena > Triangulation

Triangulation

SRM 225 · 2004-12-28 · by lars2520

SRM 225 · 2004-12-28 · by lars2520 · Geometry
Class Name: Triangulation
Return Type: String[]
Method Name: triangulate
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

A simple polygon is one where none of the sides of the polygon touch each other, except when adjacent edges touch at their endpoints. Any simple polygon can be triangulated into a number of triangles by drawning N-3 line segments between pairs of the polygon's vertices, where N is the total number of vertices. The N-3 lines must not touch each other, or any of the edges of the polygon, except where they touch at their endpoints.

Your task is, given a simple polygon, find a triangulation for this polygon. The polygon will be given as two int[]s, x and y, where there is an edge from x[i],y[i] to x[(i+1)%N],y[(i+1)%N]. You should return this triangulation as a String[], where each element is of the form "P1 P2", where P1 and P2 are the 0-based indices of the vertices in the input, and P1 < P2. Your return should be sorted first by P1, and ties should be broken by P2. If there are multiple possible triangulations, find the first element of the return for which the two differ. Choose the triangulation that has the smaller P1 in this element. If there is a tie, choose the one with the smaller P2. For example, choose {"0 2"} over {"1 3"} and {"0 2","0 3","2 4"} over {"0 2","0 4","1 3"}.

Constraints

  • x and y will each contain between 4 and 50 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element of x and y will be between -1000 and 1000, inclusive.
  • The input will represent a simple polygon, where each edge has length greater than 0, and no two adjacent edges are parallel.
Examples
0)
{0,10,10,0}
{0,0,10,10}
Returns: { "0 2" }

This input represents a square from (0,0) to (10,10), which can be triangulated by drawing a line from (0,0) to (10,10).

1)
{0,10,10,8}
{0,0,10,2}
Returns: { "1 3" }
2)
{0,5,10,10,0}
{10,5,10,0,0}
Returns: { "1 3",  "1 4" }
3)
{0,1,1,0,0,1,1,0,-1,-1}
{0,1,2,2,3,3,4,5,4,1}
Returns: { "0 2",  "0 3",  "0 8",  "3 8",  "4 6",  "4 7",  "4 8" }
4)
{0,1,1,0,1,1,0,-1,-1}
{0,1,2,2,3,4,5,4,1}
Returns: { "0 2",  "0 3",  "0 7",  "3 5",  "3 6",  "3 7" }
32)
{77,-264,-338,497,100,-71}
{-315,-174,326,323,-613,-344}
Returns: { "0 2",  "0 3",  "0 4" }

{77,-264,-338,497,100,-71,203} {-315,-174,326,323,-613,-344,-294}

55)
{-533,101,149,510,525,231}
{559,-108,284,-363,-390,728}
Returns: { "0 2",  "2 5",  "3 5" }

361 15 647 27 0.55795981452859350850077279752705 0.55555555555555555555555555555556

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

Coding Area

Language: C++17 · define a public class Triangulation with a public method vector<string> triangulate(vector<int> x, vector<int> y) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous