TopCoder problem "Hull" used in SRM 24 (Division I Level Three , Division II Level Three)



Problem Statement

    
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

 

Definition

    
Class:Hull
Method:numSegmentPoints
Parameters:int[]
Returns:int
Method signature:int numSegmentPoints(int[] param0)
(be sure your method is public)
    

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=146

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=3023&pm=146

Writer:

wluebke

Testers:

Problem categories: