ConvexHull
SRM 271 · 2005-11-08 · by Vedensky
SRM 271 · 2005-11-08 · by Vedensky · Brute Force, Dynamic Programming
Problem Statement
Problem Statement
You have a rectangle with corners at (0, 0) and (m, n). You would like to place a convex polygon inside it such that the polygon's vertices are at integer coordinates. The vertices may lie anywhere inside the rectangle or on its boundary.
You are given m and n, the dimensions of the rectangle. Return the maximal number of vertices contained by the convex polygon.
You are given m and n, the dimensions of the rectangle. Return the maximal number of vertices contained by the convex polygon.
Constraints
- m and n will be between 3 and 200, inclusive.
Examples
0)
3 3 Returns: 8
1)
3 50 Returns: 8
2)
4 4 Returns: 9
3)
4 5 Returns: 10
4)
50 200 Returns: 74
Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ConvexHull with a public method int intHull(int m, int n) · 67 test cases · 2 s / 256 MB per case