Connection Status:
Competition Arena > Skyscraper

Skyscraper

SRM 139 · 2003-03-18 · by dgoodman

SRM 139 · 2003-03-18 · by dgoodman
Class Name: Skyscraper
Return Type: int
Method Name: wire
Arg Types: (int, int, int, int, int)
Problem Statement

Problem Statement

We need to add wiring to a skyscraper that is shaped like a rectangular box. It is more than 5,000 feet tall, the front and back have a width of 200 feet, and its sides have a width of w. We need to wire from a point (xfront,yfront) on the front to a point (xright,yright) on the side to our right.

The coordinates of a point are given in positive feet, measured from the upper left corner of its face of the building. For example, if w were 300 and the two points were (xfront,yfront) = (25,75) and (xright,yright) = (275,500) they would appear approximately at the locations labeled p and q respectively in the picture.

          ___200____ 
         /         /|
        /         / |
       /         /  |
   w=300       300  |
     /         /    |
    /         /     |
   /___200___/      |
   |         |      |
   |         |      |
   |p        |      |
   |         |      |
   |         |     q|
   |         |      |
   |         |      |
   |         |      |
   |         |      |

Our wire must run along the outside of the building, but it may go over the top and along any sides. Wires come in integer lengths and we want to have as little slack as possible.

Create a class Skyscraper that contains a method wire that is given five int values w, xfront,yfront and xright,yright and that returns the length of the shortest wire that will reach between the two points. If a fractional distance is required, return the next higher integer.

Notes

  • warning: the shortest wire may run along any of the sides of the building, not just the ones that appear in the picture.

Constraints

  • w will be between 1 and 1000 inclusive
  • xfront will be between 0 and 200 inclusive
  • yfront will be between 0 and 1000 inclusive
  • xright will be between 0 and w inclusive
  • yright will be between 0 and 1000 inclusive
Examples
0)
300
200
5
0
5
Returns: 0

���� These two points are the same point, located on the edge between the front and right side of the building.

1)
300
103
50
29
50
Returns: 126

���� A horizontal wire is the shortest. It must traverse 97 feet along the front and then 29 feet along the right side.

2)
300
103
5
29
5
Returns: 108

A horizontal wire is not the shortest. The shortest wire goes diagonally up the front, across a corner of the top, and diagonally down to 29,5 on the right side. This will require about 107.52 feet of wire, so we will need a 108-foot wire.

3)
500
100
0
500
100
Returns: 539
4)
399
0
270
399
17
Returns: 628
5)
600
0
800
100
800
Returns: 300

//int w=600,x=0,y=800,xx=100,yy=800; //90,000 case ab //int w=600,x=100,y=0,xx=500,yy=100; //290000, case acb //int w=50,x=10,y=0,xx=50,yy=10; //39,700 casea cAb // //int w=600,x=0,y=100,xx=500,yy=100; //410,000 aBcb // int w=399,x=0,y=270,xx=399,yy=17; //393,956 aBcAb

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

Coding Area

Language: C++17 · define a public class Skyscraper with a public method int wire(int w, int xfront, int yfront, int xright, int yright) · 18 test cases · 2 s / 256 MB per case

Submitting as anonymous