Connection Status:
Competition Arena > Warehouse

Warehouse

SRM 177 · 2003-12-30 · by dgoodman

SRM 177 · 2003-12-30 · by dgoodman · Geometry
Class Name: Warehouse
Return Type: int
Method Name: feetWide
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Our warehouse is square, 200 feet on each side, with solid north and south walls. The east and west walls have sliding doors which allow trucks free entry and exit. Trucks come in a variety of sizes, but the width of each truck is an integer number of feet. Unfortunately the roof is supported by posts (of negligible size).

We want to drive big trucks in a straight line into the warehouse through the west wall and (after unloading and without changing direction) out through the east wall. Create a class Warehouse that contains the method feetWide that takes the positions of the posts as inputs and returns the width of the widest truck (of integral width) that can drive straight through without touching any posts (or the north or south wall). The positions of the posts are given by int[] x and int[] y: the i-th element of x and y gives the distance in feet east and north respectively from the southwest corner of the building to the i-th post.

Constraints

  • x has between 1 and 50 elements inclusive
  • y has the same number of elements as x
  • each element of x and y is between 0 and 200 inclusive
Examples
0)
{0}
{200}
Returns: 199

The only post is at one of the corners of the building.

1)
{100,100,120}
{60,140,180}
Returns: 79

The best path is due east, but the first and second posts are only 80 feet apart so the truck must be less than 80 feet wide.

2)
{100,120}
{60,140}
Returns: 82

The best path is a little south of east, going between the two posts. The distance between the posts is sqrt(6800) = 82.xxx

3)
{40,80,120}
{80,40,160}
Returns: 101
4)
{0,0,100}
{50,100,150}
Returns: 89

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 Warehouse with a public method int feetWide(vector<int> x, vector<int> y) · 21 test cases · 2 s / 256 MB per case

Submitting as anonymous