Class name: Hull
Method name: numSegmentPoints
Parameters: int[]
Returns: int
Given a set S of points in the two-dimensional plane, return the number of
points of the smallest convex set containing S. The points in this convex set
must be in S. Think of the shape assumed by a rubber band that has been
stretched around pegs at each point in S and released to conform as closely as
possible to the pegs - and return the number of points in S required to keep
that shape of the elastic. If S has no points, then the smallest convex set is
the empty set, so 0 should be returned.
Input: A int[] S of elements where every two numbers is an x and a y
coordinate of a point. (Duplicate points are to be ignored.)
Output: The number of points of the smallest convex set containing S. (For
example, if the convex set is a triangle, return 3, a square, return 4, etc.)
Here is the method signature (be sure your method is public):
int numSegmentPoints(int[] S);
S is guaranteed to contain no more than 25 points (50 elements). The
coordinates are guaranteed to be no less than -1000 and no greater than 1000.
S contains an even number of values. TopCoder will check all this.
Examples:
If the int[] is {-5, 0, 3, -10, 3, 10, 10, 5, 10, -5, 0, 0, 2, -2}
The Points: (-5,0) (3,-10) (3,10) (10,5) (10,-5) (0,0) (2,-2)
The first 5 are vertices of a convex polygon that contains all the points of S
(marked with a #) and the others are inside (*). So the method should return
5. (Note that the above points could be entered in any order provided the
pairs are kept together - and the result would still be 5).
10 #
9
8
7
6
5 #
4
3
2
1
0 # *
-1
-2 *
-3
-4
-5 #
-6
-7
-8
-9
-10 #
100000000000000000001
098765432101234567890
(negative)
Input: S = {10, 34}
Output: 1
Input: S = {0, 0, 10, 0, 5, 10, 5, 2}
Output: 3
Input: S = {0, 0, 0, 10, 10, 10, 10, 0, 5, 5}
Output: 4
Input: S = {0, 0, 1, 1, 2, 2}
Output: 2
|