Statistics

Problem Statement for "AllWoundUp"

Problem Statement

Given a closed path in the plane (which may intersect itself or even retrace itself), each point that is not on the path has a unique "winding number" that tells how many times the path winds around that point. As the path is traced out, the direction from the point to the path changes continuously and after the path has been completed the total change is an integral number of complete rotations. A negative result indicates that the path wound around the point in a clockwise direction.

For example in the following diagram where paths are straight line segments from number to number,

  • For the path 13421 the winding number of P is 1
  • For the path 13421231 the winding number of P is 0 (+1 + -1 = 0)
  • For the path 124312431 the winding number of P is -2
  • For the path 421234 the winding number of P is 0

        1               2
                  P
                  3      4

We are interested in the winding numbers for the points along the x axis. We are given the vertices of a piecewise linear closed path in the order in which the path is traced (the final segment is the one from the last given vertex to the first given vertex). Create a class AllWoundUp that contains a method maxWind that is given the vertices in int[]s x and y and that returns the largest non-negative winding number among all the points on the x axis (that are not on the path).

Definition

Class:
AllWoundUp
Method:
maxWind
Parameters:
int[], int[]
Returns:
int
Method signature:
int maxWind(int[] x, int[] y)
(be sure your method is public)

Constraints

  • x contains between 1 and 50 elements, inclusive.
  • y contains the same number of elements as x.
  • Each element of x and of y is between -1000 and 1000, inclusive.

Examples

  1. {1,4}

    {-2,9}

    Returns: 0

    This closed path has 2 segments that retrace each other. All points in the plane that are not on the path have a winding number of 0.

  2. {1,1,3,3}

    {-1,0,0,1}

    Returns: 0

    This closed path has one region (inside the triangle (2,0),(3,0),(3,1)) in which all the points have a winding number of 1, and another triangular region with a winding number of -1. But no point on the x axis is in either of these regions.

  3. {0,1,1,0,2}

    {1,-1,1,-1,1}

    Returns: 2

    This path, in addition to its exterior, has 4 regions with a winding number of 1, and 1 region with a winding number of 2. The section of the x axis between 1/2 and 1 is in that region.

  4. { 0,1000, 500, 0,1000, 500, 500,1000, 0, 500,1000, 0}

    {-100,-100, 100,-100,-100, 100, 100,-100,-100, 100,-100,-100}

    Returns: 0

    This path winds around its interior region 2 times counterclockwise, but then backtracks winding around its interior region 2 times clockwise. As a result both its exterior and its one interior region have winding number 0.

  5. { 0,1000, 500, 0,1000, 500, 500,1000, 0, 500}

    {-100,-100, 100,-100,-100, 100, 100,-100,-100, 100}

    Returns: 1

    As the path is traced out, the angle from the point to the path changes continuously and after the path has been traced is an integral number of complete rotations.

  6. {0, 0, 1, 1}

    {0, 1, 1, 0}

    Returns: 0

  7. {0, 1, 1, 0}

    {0, 0, 1, 1}

    Returns: 0

  8. {-1, 1, 0}

    {-1, -1, 1}

    Returns: 1

  9. {1, -1, 0}

    {-1, -1, 1}

    Returns: 0

  10. {-1, 1}

    {7, 7}

    Returns: 0

  11. {-1,1}

    {0,0}

    Returns: 0

  12. {-7,-7}

    {5,-2}

    Returns: 0

  13. {3}

    {0}

    Returns: 0

  14. {-2}

    {-2}

    Returns: 0

  15. {-73, 57, 24, 57, -45, -11, 20, -83, -15, 48, 27, 15, 59, -15, 0, 41}

    {50, -15, 90, -23, -13, 98, -23, 65, -7, -67, -78, 77, 34, 25, -58, 20}

    Returns: 1

  16. {96, 24, -95, -14, 59, 41, 28, -85, 91, 94, -27, 44, -21, 83, 6, -18, -23, -54, -77, 85, 19, 26, -55, -9, 34}

    {8, -46, 87, -64, -35, 34, -78, 30, 35, 99, -1, -8, 64, 27, 24, 24, 86, 7, -50, -80, 58, -71, -76, -31, -51}

    Returns: 2

  17. {82, 53, 67, -55, -23, -58, -48, 64, -79, -26, 16, -8, 53, 11, -83, -22, -45, -7, 55, 98, 50, -41, 10, -43, 78, -28, -27, 33, -40}

    {-52, -100, 74, -59, 74, 73, -50, 48, 84, 34, 30, -76, -8, 19, 81, -17, -47, -38, -92, 88, 88, 94, 89, -69, 0, 0, -41, -60, 54}

    Returns: 1

  18. {-95, -87, -75, -8, -29, 99, -68, 81, 56, -24, -29, -100, -51, -64, 24, 14, -56, 88, -48, 38, -15, 37, -43, 59, 58, 100, 67, 96, 16, 12, -92, 22, 46, 70, -76, 83, 87, -65, -74, 32, -96, -39, -73, 36, 30, -89}

    {-8, 87, 96, -72, -86, -33, -26, 47, -69, -67, 0, 0, 79, -36, 78, 97, 3, 13, -85, 97, 59, -49, 25, -31, 91, 77, -31, 69, 71, -81, -69, 46, 75, 65, 65, 12, 18, -35, -84, -14, 63, -96, -78, 35, 48, -87}

    Returns: 0

  19. {51, 7, -53, -27, -79, 55, -60, 45, -45, -48, 45, 73}

    {32, 0, 0, -2, -60, 68, -55, -45, 72, -37, -49, 63}

    Returns: 2

  20. {28, -86, -16, -70, -45, 53, 86, 53, -62, -50, -87, 67, 35, 77}

    {-39, 17, 55, 9, -33, 70, 61, -36, 20, 73, 0, 0, -47, 81}

    Returns: 0

  21. {-63, -99, 30, -89, -21, 17, 32, -47, 75, 31, -58, -58, -25}

    {-97, -48, -69, 85, -30, 44, -15, 6, -57, 0, 0, 61, -94}

    Returns: 0

  22. {-5, 3, 4, 7, 4, 0, -9, 12, 4, 0}

    {2, -11, 11, 13, -15, 11, 0, 0, -4, 13}

    Returns: 0

  23. {-1, 7, 1, 8, -5, 11, 10, -3, 12, -13, -8, -7}

    {-6, 0, 0, -9, -4, 5, 13, -6, -4, 6, -5, 11}

    Returns: 1

  24. {8, 4, -6, 3, 12, -8, 13, -3, 2, -9, 8, 4}

    {6, 15, -15, -11, 14, 0, 0, -4, -7, -14, -4, 10}

    Returns: 0

  25. {-15, 13, 6, -1, 2, 11, -3, -14, -15, 5, -5, 14}

    {-10, 5, 6, -1, 10, -2, 7, -9, 0, 0, 14, 13}

    Returns: 0

  26. {7, 8, 0, -15, -15, -4, 5, -10, -6}

    {-8, -7, -11, 2, 2, -7, 2, -2, 3}

    Returns: 1

  27. {2, 0, 1, -3, 14, -7, -7, 0, 3, 7, -10, -10}

    {-2, 12, -3, -15, -11, 1, 4, -9, 14, 12, 1, 1}

    Returns: 2

  28. {-8, 2, 10, 12, -7, 8, 0, -14, -11, -7, -6}

    {3, -13, 12, 3, 13, 5, 0, 0, 5, -14, -2}

    Returns: 1

  29. {14, 13, -15, -3, 11, 5, 8, 11, 7, 14, -14}

    {8, 2, -14, -12, -1, 5, -12, 1, 0, 0, 15}

    Returns: 1

  30. {-9, -12, -2, 12, 7, -7, 14, -10, -8, 10}

    {0, 6, 15, 15, -6, -10, -1, 8, 2, 0}

    Returns: 1

  31. {12, -11, 10, 15, -9, -9, 14, -4, 3}

    {-9, 0, 0, 10, 9, -13, -4, 11, -13}

    Returns: 0

  32. {-3, 4, 6, -12, -1, -1, -14, 14, -15, -5, -14, 12}

    {8, -8, -10, 13, -10, 14, 5, 15, 8, -10, 0, 0}

    Returns: 0

  33. {-14, -6, 11, -13, -13, -11, 13, -7, -4, 0, -1, -3}

    {-5, -13, 6, -3, -3, -5, 11, 7, -10, -8, -14, 4}

    Returns: 3

  34. {-8, -15, 2, -13, 8, 0, -8, -13, -8, -14, 9}

    {-3, -11, 15, 3, 9, 0, 0, -9, -2, -7, 4}

    Returns: 1

  35. {12, -9, 12, -7, -1, 13, 15, 2, 5, -4, 1}

    {-10, -10, 13, -11, 2, -5, 0, 5, 0, 0, 3}

    Returns: 1

  36. {-6, 4, -6, -3, 1, -3, -2, -3}

    {0, 8, 3, -3, 7, 0, 6, 0}

    Returns: 1

  37. {-6, 4, -6, -3, 1, -3}

    {0, 8, 3, -3, 7, 0}

    Returns: 1

  38. {-6,-3, 1, -3}

    {0, -3, 7, 0}

    Returns: 1

  39. {2, 3, 3, -6, 6, 6, 3, -8, -5, 7}

    {1, -6, 1, 3, 3, 3, 6, -7, 6, -5}

    Returns: 2

  40. {4, -6, -6, 7, 0, 9, 7}

    {0, 5, 5, -7, 6, 3, 3}

    Returns: 1

  41. {4, -6, 7, 0, 9, 7}

    {0, 5, -7, 6, 3, 3}

    Returns: 1

  42. {-15, 7, -10, -7, -12, -15, -6}

    {-10, 6, 0, 0, 0, 7, 14}

    Returns: 1

  43. {-15, 7, -10, -12, -15, -6}

    {-10, 6, 0, 0, 7, 14}

    Returns: 1

  44. {-11, 7, -10, -7, -12, -15, -6}

    {-10, 6, 0, 0, 0, 7, 14}

    Returns: 1

  45. {0, -9, 10, 10, 13, -14, -9, 2, -4}

    {-1, 0, -6, -12, 2, 11, 0, 0, 0}

    Returns: 1

  46. {-11, 7, -10, -7, -12}

    {-10, 6, 0, 0, 0}

    Returns: 1

  47. {3,1,6,2,0}

    {0,0,0,49,-49}

    Returns: 0

  48. {0, 2, 1 }

    {-1, 1000, 1000 }

    Returns: 1

  49. {0, -1, -1, 0, 0, 0, -1, -1, -1, 0, 1, 1, 0, 0, 1, 2, 2, 2, 1, 0, 0, 1, 1, 0, 0 }

    {1, 1, -1, -1, 0, 1, 1, 0, -1, -1, -1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, 0, 1, 1, 0 }

    Returns: 2

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.
This problem was used for: