MakePolygon | Topcoder Archive

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 (x₀, y₀), (x₁, y₁), (x₂, y₂), ..., (x_N-1, y_N-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 x_i * 100 + y_i. If there are multiple optimal polygons, you may return any of them.

Definition

Class:: MakePolygon
Method:: make
Parameters:: int
Returns:: int[]
Method signature:: int[] make(int N)
(be sure your method is public)

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

```
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.
```
4
```
```
Returns: {101, 201, 202, 102 }
```
```
5
```
```
Returns: {101, 201, 303, 202, 102 }
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.