Connection Status:
Competition Arena > MakePolygon

MakePolygon

TCO 19 SRM 739 · 2018-10-09 · by Blue.Mary

TCO 19 SRM 739 · 2018-10-09 · by Blue.Mary · Math
Class Name: MakePolygon
Return Type: int[]
Method Name: make
Arg Types: (int)
Problem Statement

Problem Statement

You are given an int N. Your task is to generate any (not necessarily convex) polygon P such that:

  • The number of vertices of P must be exactly N.
  • P must be simple. (See Notes for the definition.)
  • Each coordinate of each vertex of P must be an integer between 1 and 25, inclusive.
  • P must have the smallest possible area (among all polygons that satisfy all previous constraints).

Suppose the vertices of the polygon you generated are (x0, y0), (x1, y1), (x2, y2), ..., (xN-1, yN-1) in order along its boundary (in either direction). Return a int[] with N elements. For each i, element i of the return value should be xi * 100 + yi. If there are multiple optimal polygons, you may return any of them.

Notes

  • A simple polygon is a polygon such that the length of each side is positive, no two consecutive sides are parallel, and no two non-consecutive sides share a common point.
  • For the given constraints there is always at least one polygon that satisfies all the constraints.

Constraints

  • N will be between 3 and 500, inclusive.
Examples
0)
3
Returns: {101, 201, 102 }

The example return value describes a triangle with vertices at (1,1), (2,1), and (1,2). The area of this triangle is 0.5, which is optimal.

1)
4
Returns: {101, 201, 202, 102 }
2)
5
Returns: {101, 201, 303, 202, 102 }
3)
6
Returns: {205, 104, 203, 303, 204, 305 }
4)
7
Returns: {106, 205, 104, 203, 303, 204, 305 }

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

Coding Area

Language: C++17 · define a public class MakePolygon with a public method vector<int> make(int N) · 119 test cases · 2 s / 256 MB per case

Submitting as anonymous