TopCoder Statistics - Problem Statement

Problem Statement

Alice is a high school student. One day, her teacher asked her to draw a simple polygon (see Notes for a definition). The polygon must satisfy two conditions:

First, each of its vertices must be at a grid point. (I.e., both coordinates of each vertex must be integers.)

Second, the perimeter of the polygon must be exactly equal to the integer L.

You are given the int L. If there is no such polygon, return -1. If there is at least one such polygon, find the one which has the least number of sides. If there are still more than one choice, find the one with the smallest possible difference between the lengths of its longest side and its shortest side. Return the difference between the lengths of its longest side and its shortest side.

Definition

Class:: FindPolygons
Method:: minimumPolygon
Parameters:: int
Returns:: double
Method signature:: double minimumPolygon(int L)
(be sure your method is public)

Notes

A simple polygon is a polygon such that no two consecutive sides are parallel and no two non-consecutive sides share a common point.
Return values with absolute or relative error at most 1e-9 will be accepted as correct.

Constraints

L will be between 1 and 5000, inclusive.

Examples

1

Returns: -1.0
2

Returns: -1.0
3

Returns: -1.0
4

Returns: 0.0

There is no triangle whose perimeter is 4, but there is a square.
5

Returns: -1.0

There is no simple polygon that matches all the constraints.
6

Returns: 1.0
12

Returns: 2.0

There is a triangle whose sides are 3, 4, 5.
14

Returns: 1.0
16

Returns: 1.0
18

Returns: 3.0
20

Returns: 0.0
60

Returns: 10.0
62

Returns: 1.0
64

Returns: 4.0
66

Returns: 19.0
68

Returns: 9.0
70

Returns: 9.0
72

Returns: 6.0
74

Returns: 1.0
76

Returns: 18.0
78

Returns: 22.0
80

Returns: 5.0
82

Returns: 1.0
84

Returns: 4.0
86

Returns: 1.0
88

Returns: 18.0
90

Returns: 11.0
92

Returns: 0.0
94

Returns: 1.0
96

Returns: 6.0
98

Returns: 11.0
100

Returns: 2.0
102

Returns: 1.0
104

Returns: 15.0
106

Returns: 1.0
108

Returns: 9.0
110

Returns: 27.0
112

Returns: 7.0
114

Returns: 26.0
116

Returns: 0.0
118

Returns: 1.0
120

Returns: 20.0
122

Returns: 1.0
124

Returns: 0.0
126

Returns: 6.0
128

Returns: 8.0
130

Returns: 11.0
132

Returns: 22.0
134

Returns: 1.0
136

Returns: 18.0
138

Returns: 1.0
140

Returns: 18.0
142

Returns: 1.0
144

Returns: 9.0
146

Returns: 1.0
148

Returns: 0.0
4999

Returns: -1.0
4953

Returns: -1.0
99

Returns: -1.0
3001

Returns: -1.0
4948

Returns: 0.0
4954

Returns: 1.0
4962

Returns: 1627.0
5000

Returns: 74.0
4984

Returns: 819.0
4894

Returns: 1.0
2910

Returns: 10.0
3918

Returns: 1231.0
196

Returns: 1.0
156

Returns: 2.0
150

Returns: 3.0
154

Returns: 31.0
1164

Returns: 4.0
4356

Returns: 6.0
722

Returns: 1.0
4906

Returns: 929.0
36

Returns: 3.0
4780

Returns: 1463.0
4964

Returns: 657.0
40

Returns: 9.0
15

Returns: -1.0

Statistics

Problem Statement for "FindPolygons"

Problem Statement

Definition

Notes

Constraints

Examples