Connection Status:
Competition Arena > Tether

Tether

TCCC '03 W/MW Regional · 2003-02-20 · by dgoodman

TCCC '03 W/MW Regional · 2003-02-20 · by dgoodman · Geometry
Class Name: Tether
Return Type: int
Method Name: deadTrees
Arg Types: (int, int, vector<int>, vector<int>)
Problem Statement

Problem Statement

We have a goat. We want to tether him with a long rope to the only solid structure we have in our orchard, a cylindrical water tank with its round base sitting on the ground. We are worried that the goat will be able to get at our fruit trees and will destroy them.

The rope will be attached at the southernmost point on the water tank. The rope cannot pass through the water tank, so as the goat tries to reach some of our trees the rope may wrap part way around the circular base of the tank.

Create a class Tether that contains a method deadTrees that takes the length of the rope, the radius of the water tank, and the locations of our trees and returns the number of trees that the goat will be able to reach. The locations of our trees are given by int[] x and int[] y, the distances east and north respectively from the center of the tank.

Notes

  • x and y give the coordinates east and north of the tank's center
  • the goat will be tethered at the southernmost point on the tank, (0,-radius)
  • if the goat can just exactly reach a tree, count the tree as dead
  • the rope can not pass through the tank, but it is not impeded by trees (since they would have been eaten all the way down to the ground)
  • it has been verified that none of the allowed inputs can lead to significant rounding errors. (There are no attainable distances that are within 1E-10 of an integer, and are not exactly an integer).

Constraints

  • rope is between 1 and 300 inclusive
  • radius is between 1 and 300 inclusive
  • x contains between 1 and 50 elements
  • y contains the same number of elements as x
  • each element of x and y is between -300 and 300 inclusive
  • each location (xi,yi) is distinct from each other location
  • xi*xi + yi*yi > radius*radius for each element of x and y (so no trees are inside the tank)
Examples
0)
30
10
{0,0,0}
{-11,-12,11}
Returns: 2

The goat is tethered at (0,-10) and can easily reach the first two trees. If the tank were not in the way, the goat could get to the northern tree, but the distance is greater than 30 going around the tank.

1)
30
10
{0,-11,-10,-10}
{-30,0,14,15}
Returns: 3

The first tree can just be reached -- count it. The second tree is easily reached going clockwise around the tank. The third tree can be reached by going 1/4 of the way around the tank and then straight north, but the fourth tree is out of reach.

2)
31
10
{0,-11,-10,-10}
{-30,0,14,15}
Returns: 4

This is the same as the previous example but with the rope slightly longer.

3)
30
10
{0,-11, 10,-10}
{-30,0,14,15}
Returns: 3
4)
200
100
{100,100,100,100,-100,100}
{1,-273,-274,42,42,43}
Returns: 4

Submissions are judged against all 21 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Tether with a public method int deadTrees(int rope, int radius, vector<int> x, vector<int> y) · 21 test cases · 2 s / 256 MB per case

Submitting as anonymous