Connection Status:
Competition Arena > Watchtower

Watchtower

SRM 176 · 2003-12-22 · by Running Wild

SRM 176 · 2003-12-22 · by Running Wild · Geometry
Class Name: Watchtower
Return Type: int[]
Method Name: orderByArea
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You have been put in charge of allocating men and resources to watchtowers in a particular region. You have decided to determine how many resources to allocate to each watchtower by determining how much area each watchtower has to watch. You will determine the area that a watchtower is responsible for watching by finding the region around that watchtower for which every point in that region is closer to that watchtower than to any other watchtower.

You've modeled the n watchtowers as points in the x-y plane, each assigned an index between 0 and n-1, inclusive. The total region that needs to be watched is the square region with corners at (0,0) and (100,100). The region that a watchtower must watch does not extend outside of this region. Create a class Watchtower with a function orderedByArea that takes two int[]s, x and y, representing the x and y coordinates of the watchtowers, and returns a int[] that contains the index of each watchtower ordered by how much area each one is responsible for, with the index of the watchtower responsible for the most area first. The i-th elements of x and y represent the coordinates of the i-th watchtower.

Constraints

  • x and y will contain between 1 and 20 elements, inclusive.
  • x and y will both contain the same number of elements.
  • Each element of x and y will be a value between 0 and 100, inclusive.
  • Every point represented by x and y will be unique.
  • To avoid rounding errors, the area that two watchtowers are responsible for watching will never differ by less than 1e-5.
Examples
0)
{10,50}
{10,50}
Returns: { 1,  0 }

The watchtower at (10,10) is in the corner and only has to watch the area defined by the triangle with points at (0,0), (60,0), and (0,60), which is an area of 1800. The watchtower at (50,50) must watch the rest of the territory, which is an area of 8200, so the method returns {1,0}.

1)
{0,1,98,97}
{0,99,98,3}
Returns: { 3,  2,  1,  0 }

Each watchtower is near one of the corners, and the ones that are closer to the center have slightly more area to watch than ones that are further from the center.

2)
{25}
{25}
Returns: { 0 }

If there is only one watchtower it has to watch all of the territory on its own.

3)
{10,40,50,50,90}
{10,40,50,75,50}
Returns: { 3,  4,  1,  0,  2 }
4)
{6,19,38,47,49,61,63,65,65,71,85}
{74,52,70,95,1,55,79,0,32,93,99}
Returns: { 1,  8,  5,  4,  0,  2,  7,  6,  3,  10,  9 }

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

Coding Area

Language: C++17 · define a public class Watchtower with a public method vector<int> orderByArea(vector<int> x, vector<int> y) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous