FindPolygons
SRM 599 · 2013-06-25 · by standy
SRM 599 · 2013-06-25 · by standy · Brute Force, Geometry, Search, Simple Math
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 theint 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.
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
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
0)
1 Returns: -1.0
1)
2 Returns: -1.0
2)
3 Returns: -1.0
3)
4 Returns: 0.0
There is no triangle whose perimeter is 4, but there is a square.
4)
5 Returns: -1.0
There is no simple polygon that matches all the constraints.
6)
12 Returns: 2.0
There is a triangle whose sides are 3, 4, 5.
Submissions are judged against all 81 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FindPolygons with a public method double minimumPolygon(int L) · 81 test cases · 2 s / 256 MB per case