Statistics

Problem Statement for "DogWoods"

Problem Statement

This problem uses subscripts and superscripts which may not display properly for plugin users.

We've all heard the riddle "How far can a dog run into the woods?", where the expected answer is "halfway". However, this is only correct if worded as "How far can a dog run directly into the woods?". We're here today to solve the actual problem, where "running into" is defined as moving in a way such that for any two times t1>0 and t2>0, t1<t2 if and only if distance(position(t1))>distance(position(t2)), where distance(p) is the distance (in a straight line) from the center of the woods to a position, and position(t) is the dog's position at time t. Complicating (and making more realistic) our problem are the trees in the woods. Each tree is defined by x and y coordinates, and a diameter. As any dog owner can attest, it is in a dog's nature to run in circles. Our dog is slightly demented, so his nature is to run in clockwise circles centered at the center of the woods until he hits a tree. If he hits a tree, he runs counterclock-wise around the tree until he is able to travel clockwise tangent to the center of the woods.

You are to create a class DogWoods, with a method howFar, which takes int[]s containing the x and y coordinates, and the diameters of each tree. The method will also take parameters startx and starty, which are the starting x and y coordinates for the dog. The ith element of x corresponds to the ith element of y, which corresponds to the ith element of diameter. The dog is determined to have reached the center of the woods when the dog's distance to the center is <= 10 units. Your method must return the distance that would be travelled by the dog, while obeying his nature, before he reaches the center of the woods. Your return value must be within 1e-9 relative or absolute error of the correct value.

The location (0,0) is the center of the woods, with the positive x axis extending to the right, and the positive y axis extending up (a standard Cartesian plane).

If the dog would run an infinitely long distance while obeying his nature, then your method should return -1.

Given two circles with the following equations,

(x - x0)2 + (y - y0)2 = r02 (A circle centered at (x0,y0) with radius r0)
x2 + y2 = r12 (A circle centered at (0,0) with radius r1)

their points of intersection are given by:

x = x0 / 2 - x0(r02 - r12) / 2d + y0p / 2d
y = y0 / 2 - y0(r02 - r12) / 2d - x0p / 2d
and
x = x0 / 2 - x0(r02 - r12) / 2d - y0p / 2d
y = y0 / 2 - y0(r02 - r12) / 2d + x0p / 2d
where
d = x02 + y02
p = sqrt(((r0 + r1)2 - d)(d - (r1 - r0)2))

Definition

Class:
DogWoods
Method:
howFar
Parameters:
int[], int[], int[], int, int
Returns:
double
Method signature:
double howFar(int[] x, int[] y, int[] diameter, int startx, int starty)
(be sure your method is public)

Notes

  • The dog will always obey his nature as described.
  • The dog may not run through any part of a tree.
  • Trees are to be considered exactly round.
  • The dog should be treated as a mathematical point. I.e., it has no diameter.
  • The distance around a circle is pi * diameter.
  • pi ~ 3.14159265358979.

Constraints

  • x, y, and diameter will all have the same number of elements.
  • x will have between 1 and 50 elements, inclusive.
  • Every element of x and y will be between -1000 and 1000, inclusive.
  • Every element of diameter will be between 1 and 100, inclusive.
  • startx and starty and will be between -1000 and 1000, inclusive.
  • The closest that the perimeter of any two trees will be to each other is 1e-6.
  • For any two trees a and b, the distance of the closest point to the center of a will not be within 1e-6 of the distance of the furthest point to the center of b.
  • No tree will completely cover the circle of diameter 20 at the center of the woods.
  • For every tree, the circle of diameter 20 will either not intersect that tree, or it will intersect by at least 1e-6 units at the greatest width of intersection.
  • The dog will not start in the midst of a tree.

Examples

  1. {0}

    {10}

    {10}

    -14

    0

    Returns: 23.64281561414452

    The dog travels until it meets the tree, covering 18.431923291703267 units, and then travels around the tree until it is within 10 units of the center, for another 5.2108923224412536 units. In the image, the red lines represents the dog's path, the black circle the tree, and the blue circle the center of the forest.

  2. {40,15,-5}

    {7,25,11}

    {26,12,23}

    0

    -49

    Returns: 531.3835950099849

    In this image, the red lines represents the dog's path, the black circles the trees, and the blue circle the center of the forest.

  3. {3}

    {3}

    {3}

    12

    12

    Returns: -1.0

    The dog can continue spiraling around the center never meeting a tree.

  4. {15}

    {15}

    {1}

    5

    8

    Returns: 0.0

    The dog started within 10 units of the center, and therefore cannot travel any further.

  5. {-220,-204,-187,-11,16,211,-180,87,272,-118,-1,16,187,113,71,217,-12,78}

    {232,-162,60,-125,-22,-266,-120,-242,87,-148,50,-218,161,-232,249,215,11,-79}

    {53,8,77,74,4,42,36,31,73,84,67,59,33,18,94,87,13,59}

    51

    -255

    Returns: 3564.170613418495

  6. {14}

    {5}

    {10}

    0

    -19

    Returns: 91.16341808491504

  7. {95,29,-86,-72,82,-164,-131,138,8,236,-248,-148,170,-85,135,64,-78,-240,-210,-239,-247,264,-140,-152,291,-6,227,115,257,273,-37,-6,143,-8,95,-182,-114,-187,-176,-189,209,47,-105,246,23,43,107,-264,-216,-204}

    {179,-289,119,-75,54,128,-143,-56,-209,-281,-100,186,126,-167,-193,274,43,-14,5,-221,-289,206,-5,283,139,45,-41,256,41,-132,-241,295,14,182,-109,-238,-222,48,67,87,-103,212,252,268,-42,124,-150,-178,194,149}

    {43,55,64,86,82,45,34,83,70,89,44,73,83,64,32,33,32,1,51,66,12,34,37,31,71,78,26,51,50,82,21,21,22,53,37,47,35,3,1,42,43,39,78,72,57,64,42,21,30,39}

    -267

    -201

    Returns: 1636.004079011533

  8. {70,262,-31,142,-221,-18,61,282,158,-120,-104,133,113,-12,-81,-77,222,-255,248,-235,-216,-40,-109,181,273,-155,15,-251,297,-136,-284,-298,49,-276,271,256,213,-235,295,70,-155,70,-294,-192,-99,-184,189,-11,118,-75}

    {248,123,167,139,210,-271,49,-154,237,106,-11,-39,294,104,-75,88,-243,-163,254,-72,-96,-156,-112,-138,47,263,28,-242,209,-232,296,235,-30,136,-95,-143,124,90,-265,-255,-34,-85,6,41,-154,-148,-284,-80,22,271}

    {61,27,56,41,65,32,21,27,25,45,50,24,23,62,26,44,32,52,74,22,30,61,24,54,58,44,45,89,50,81,65,42,34,34,35,21,62,80,56,32,34,66,75,32,48,62,56,22,61,77}

    179

    148

    Returns: 1413.0256319959615

  9. {-189,273,-281,140,-139,-112,77,-8,252,228,-251,-11,-210,11,-231,269,291,17,-26,-215,98,152,124,78,52,-140,297,-21,-76,279,188,-261,-209,276,-289,-290,167,-81,47,69,176,-221,-29,224,216,-81,176,204,-160,-151}

    {-95,-295,-219,39,-267,281,-44,-192,-34,19,277,-50,197,194,115,168,226,-298,12,19,-211,-252,268,-121,78,162,-173,156,-193,-100,-47,-118,-150,295,-284,-88,189,-74,260,287,265,-248,276,119,113,-13,-272,-206,-155,97}

    {70,51,28,89,79,56,60,37,52,63,50,29,27,43,81,93,1,1,30,99,71,35,42,44,92,95,70,53,58,32,44,27,35,79,51,41,2,2,11,13,58,26,50,12,3,28,24,53,62,35}

    103

    9

    Returns: -1.0

  10. {114,-248,-48,-20,44,-180,6,-204,-270,-119,91,244,-172,177,-275,253,175,-238,66,268,138,32,293,-204,-297,192,41,-6,-105,-60,-211,-65,62,-113,31,211,-293,114,-158,95,148,263,141,28,239,38,-181,-288,221,126}

    {-89,20,-287,149,-3,-68,22,-147,192,120,279,-81,-290,30,-165,172,273,-229,174,273,-196,-262,46,168,128,-195,-200,-58,-290,-6,-8,284,-68,232,-128,140,-68,101,-215,15,-236,-202,210,-288,221,106,254,41,-282,-299}

    {57,25,46,66,42,78,29,68,30,71,34,97,67,89,58,40,60,83,34,73,36,31,35,77,96,68,61,43,42,68,45,31,47,50,74,47,65,69,75,61,26,40,62,21,32,60,45,38,54,45}

    -16

    32

    Returns: 50.53156658741588

  11. {105,-183,251,-288,-109,-45,-186,-23,179,-266,0,253,-248,261,272,-264,55,67,115,291,-9,-239,-71,202,-80,-228,-142,298,49,-82,24,33,-156,201,248,181,-297,-114,84,141,120,104,-66,126,103,-202,-135,182,150,241}

    {-11,3,177,-182,-168,144,103,-173,-289,12,-55,52,-222,-15,-192,130,263,-134,-243,-260,295,-90,239,-178,-15,241,163,-137,-176,76,226,-275,-46,29,254,-72,-143,-60,99,-115,238,-213,-114,-223,-177,-298,193,136,-177,-260}

    {25,37,58,41,77,41,43,60,63,30,62,33,70,58,31,53,48,48,22,31,37,56,98,23,80,80,30,87,35,93,22,76,41,45,53,51,26,32,70,45,58,23,39,23,23,60,26,58,50,35}

    -161

    32

    Returns: -1.0

  12. {-264,265,289,247,-147,174,-128,-177,91,-283,7,143,-135,-100,210,108,-99,166,-10,-288,37,-46,80,52,-200,97,63,-230,284,-86,-235,-137,-186,265,242,165,-294,-28,181,102,-50,-186,-110,274,180,153,295,281,50,-33}

    {1,98,-3,-241,-106,-67,191,28,258,297,38,-287,282,137,81,106,-219,246,-60,-164,-176,-286,205,-58,156,11,-290,-257,49,236,87,227,299,216,-212,-142,-112,233,-204,-90,164,-176,-39,-159,7,137,-87,296,136,-3}

    {86,38,37,28,79,47,25,89,68,60,74,90,47,69,71,40,66,64,38,24,52,67,39,34,70,80,21,88,31,21,40,43,37,68,30,45,75,62,44,81,29,59,66,43,37,25,68,63,28,29}

    164

    103

    Returns: 989.5402927906854

  13. {269,166,-94,-132,-211,9,-89,-54,-246,29,148,-141,203,-67,62,-25,247,-111,259,193,-142,-142,-266,216,-87,272,19,-182,-7,-247,106,-129,70,-264,-197,239,-239,-198,-248,197,104,258,-48,-1,-99,47,-258,171,71,208}

    {11,268,-93,242,-131,235,-232,211,126,77,-161,-160,37,-287,-264,-130,179,136,-88,239,-31,73,34,-255,291,-244,155,179,-220,202,165,-276,-144,238,-216,76,295,55,-33,-25,291,287,-35,-176,75,-103,-225,208,24,117}

    {45,46,66,46,32,68,92,31,66,92,98,69,22,26,77,56,89,68,39,22,61,37,50,42,41,53,50,74,27,28,81,26,21,45,38,62,28,27,44,72,42,66,60,39,32,34,27,43,21,25}

    -89

    248

    Returns: -1.0

  14. {278,-151,25,148,-164,261,-33,286,-246,142,145,-293,67,-45,-209,139,-131,-19,205,226,-154,-291,297,21,-299,113,90,34,84,-184,-232,57,299,211,278,-76,-260,-128,-265,-20,19,-182,-233,-197,113,201,123,215,211,-208}

    {245,-73,230,-57,-297,185,-176,34,32,26,234,-132,-194,27,-72,-162,-208,-270,157,291,177,151,141,-94,-276,-82,245,22,96,-176,279,-276,-255,95,-125,244,-253,-5,-56,110,-230,31,160,72,171,-204,-245,-143,-269,254}

    {55,62,82,40,98,61,91,61,57,31,71,81,69,70,37,60,28,48,22,22,92,37,38,75,26,43,31,78,71,53,21,65,93,44,64,81,34,65,62,84,32,23,60,43,69,66,37,43,40,40}

    -280

    70

    Returns: 1083.9982491357457

  15. {-28,75,74,-170,255,-159,20,207,220,-230,208,5,-220,144,129,-268,-206,-97,259,-68,-284,18,1,-93,-65,217,292,-265,-133,-101,-266,101,182,-56,255,-185,-176,-116,-45,17,63,-98,227,178,77,-208,-153,-203,-261,110}

    {117,113,-100,-292,-77,-209,-158,24,-202,-30,142,-241,213,-221,112,126,-116,279,179,-92,-64,198,161,-148,25,-291,243,-146,200,-43,276,136,-17,-199,28,40,227,15,-12,280,188,147,270,-158,-2,263,155,-80,-211,164}

    {78,26,98,86,90,48,46,30,40,34,89,50,38,75,28,23,30,68,33,63,88,37,23,21,24,84,59,38,31,45,33,23,57,61,62,92,30,37,33,75,37,74,74,28,75,40,28,37,31,34}

    -244

    95

    Returns: -1.0

  16. {122,76,-207,-194,91,-175,-61,195,-116,-291,-287,-203,230,-18,-34,189,292,165,54,-59,-27,-77,143,-29,277,20,209,-102,25,296,268,75,237,-110,-271,-232,-126,202,29,-279,92,189,105,-140,192,-8,-279,72,-242,285}

    {202,99,-254,-28,228,48,-7,270,149,-40,-196,-154,11,167,-103,135,197,39,-239,-141,-264,232,-229,80,-9,-48,-88,-52,-164,-235,144,200,289,-166,48,95,36,-24,-105,-113,-57,213,-295,268,73,-44,271,36,-91,100}

    {45,93,90,54,26,41,61,41,68,86,85,65,36,43,54,58,57,29,27,36,87,62,78,61,44,28,55,40,65,83,32,30,45,37,44,57,29,25,46,43,51,24,71,41,33,27,81,28,34,29}

    44

    -32

    Returns: -1.0

  17. {-166,-296,-88,-145,124,198,107,-231,-63,-34,247,262,92,200,73,-27,-271,237,222,124,-241,-269,-244,0,30,195,-258,51,-82,-86,-103,173,231,28,-169,-150,-178,-198,120,11,36,47,81,58,71,236,-151,-199,173,122}

    {159,-121,43,-113,105,-188,8,-57,-150,-65,227,-194,292,-267,-141,125,181,-38,-128,-268,-161,-104,-239,-279,270,58,43,204,-26,208,-294,242,125,-87,252,0,29,-272,-177,17,88,40,57,139,-31,9,209,207,-132,-93}

    {61,33,86,51,96,32,61,90,77,66,94,67,52,57,43,34,76,64,22,89,89,27,64,64,42,72,72,31,29,75,32,56,61,59,50,31,21,37,46,44,22,40,28,33,43,22,41,26,48,36}

    285

    179

    Returns: 2022.7639916975368

  18. {-220, -204, -187, -11, 16, 211, -180, 87, 272, -118, -1, 16, 187, 113, 71, 217, -12, 78 }

    {232, -162, 60, -125, -22, -266, -120, -242, 87, -148, 50, -218, 161, -232, 249, 215, 11, -79 }

    {53, 8, 77, 74, 4, 42, 36, 31, 73, 84, 67, 59, 33, 18, 94, 87, 13, 59 }

    51

    -254

    Returns: 3562.526823654883

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: