PointSeq | Topcoder Archive

Problem Statement

Given a sequence of points P and an empty result list L, you will perform the following algorithm:

1) Sort P into ascending order by x-coordinate
2) Remove the first point of P and add it to the result list L
3) Remove the first point of P and add it to the end of result list L
4) Remove the first point of P and add it to the end of result list L
5) While L has 3 or more points, and the last three points of L do not make a right turn, remove the second to last element of L
6) If P is not empty goto step 4.

3 points form a right turn if the third point falls below a line through the first two points. To simplify calculations, all of the points given will have different x-coordinates.

P will be given as two int[]s xs and ys. The kth point will have x and y coordinates determined by the kth elements of xs and ys respectively. Your method will return L as a String[] with each element formatted as "x-coord,y-coord". x-coord and y-coord should have no extra leading zeros. The elements of L should be returned in exactly the order produced by the algorithm above.

Definition

Class:: PointSeq
Method:: makeSeq
Parameters:: int[], int[]
Returns:: String[]
Method signature:: String[] makeSeq(int[] xs, int[] ys)
(be sure your method is public)

Constraints

xs will contain between 3 and 50 elements inclusive
xs will contain the same number of elements as ys
Each element of xs will be between -100000 and 100000 inclusive
Each element of ys will be between -100000 and 100000 inclusive
xs will contain no repeated elements

Examples

```
{5,10,15,20}
```
```
{5,5,5,4}
```
```
Returns: { "5,5",  "15,5",  "20,4" }
```
The first 3 points get added. They do not form a right turn so the point (10,5) is removed. The last point is added. Since the 3 remaining points form a right turn we are done.

{0,5,10}

{0,5,0}

Returns: { "0,0",  "5,5",  "10,0" }

All three form a right turn.

{10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10}

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Returns: { "-10,0",  "10,0" }

No 3 points from this list will ever form a right turn.

{-3058,-6953,-2111,6350,-9345,-115,-8288,5120,-7013,-4452,-8991,439,
 -187,-6636,6493,-7694,-1258,206,-7785,4823,-7788,5081,-986,-2641,9029,
 -302,-4969,-5534,7866,-9222,9318,6776,1239,8878,-444,187,-6530,3485,
 9896,-4433,-8842,-840,9937,6264,9671,-7525,-9138,5682,4175,-5459}

{-4131,-9232,-1401,1942,-4900,2067,5353,7408,-22,9789,358,-7986,7409,
 -6401,-733,-4263,1243,1538,7568,-2141,3793,-1614,1125,4171,9563,-2577,
5378,7136,-9683,-9024,-5180,6913,5638,137,-587,6127,-1898,9055,9568,
-3729,-2772,-5821,-3659,-1359,1330,3851,8480,7688,-8584,8641}

Returns: { "-9345,-4900",  "-9138,8480",  "-4452,9789",  "9896,9568",  "9937,-3659" }

{-100000,99999,100000}

{0,20000,19999}

Returns: { "-100000,0",  "99999,20000",  "100000,19999" }

{15,5,0}

{0,0,5}

Returns: { "0,5",  "15,0" }

{-7168, 13471, 30562}

{-9537, 89464, 37788}

Returns: { "-7168,-9537",  "13471,89464",  "30562,37788" }

{0,5,10}

{0,5,10}

Returns: { "0,0",  "10,10" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.