Solar

SRM 124 · 2002-12-12 · by dgoodman

Class Name: Solar

Return Type: String

Method Name: dark

Arg Types: (int, int, int, int)

Problem Statement

We are designing a solar collector. Our design is a 6 x 6 x 6 cube, with one side being transparent to admit sunlight, and the opposite side coated with cells that collect energy. Our problem is that we need two 1 x 1 square beams running from the base to the roof to support the structure, and they block the sunlight from getting between the window and the collector.

During the course of a year, sunlight passes through the window at all possible angles. Create a class Solar that contains a method dark that will be given the location x1,y1 of one beam and the location x2,y2 of the other beam and will calculate what fraction of the collector never receives direct sunlight.

We can solve this problem by considering only a cross-section parallel to the base of the structure. Let the line segment y=0,0<=x<=6 be the window, and y=6,0<=x<=6 be the collector. In this view, each beam is a square with its sides given by x_i, y_i, x_i+1, y_i+1.

Notes

The answer must be returned in reduced form with no blanks or leading zeroes
The two beams may be in the same place. In this case there is really only one beam.
Diagonally adjacent beams touch each other, leaving no gap.(Example 0)
Return the 3 character string "0/1" if the entire collector can receive light

Constraints

x1,y1,x2,y2 all are between 0 and 5 inclusive

Examples

4
4
5
3
Returns: "1/5"

(The coordinate grid is shown. 'X' indicates a 1 x 1 beam.) 6 +-+-+-+-+-+-+ Collector | | | | | | | 5 |-+-+-+-+-+-| | | | | |X| | 4 |-+-+-+-+-+-| | | | | | |X| 3 |-+-+-+-+-+-| | | | | | | | 2 |-+-+-+-+-+-| | | | | | | | 1 |-+-+-+-+-+-| | | | | | | | 0 +-+-+-+-+-+-+ Window 0 1 2 3 4 5 6 The collector is at y=6. The window is at y=0. The left-most X is the beam which completely fills the area 4<=x<=5,4<=y<=5. For this configuration, light can reach the left part of the collector. The farthest to the right that it can reach is when light enters at the lower left corner and just misses the top left corner of the leftmost beam; this ray of light has a slope of 5/4 so it strikes the collector at x=24/5. Thus 6 - 24/5 is always dark. This is 1/5 of the collector wall so your program should return "1/5"

1
5
4
4
Returns: "1/6"

6 +-+-+-+-+-+-+ Collector | |X| | | | | 5 |-+-+-+-+-+-| | | | | |X| | 4 |-+-+-+-+-+-| | | | | | | | 3 |-+-+-+-+-+-| | | | | | | | 2 |-+-+-+-+-+-| | | | | | | | 1 |-+-+-+-+-+-| | | | | | | | 0 +-+-+-+-+-+-+ Window 0 1 2 3 4 5 6 Light can go to the left of the leftmost beam, and can also go through the gap between the 2 beams and to the right of the right beam. The left area is obviously 1 unit. The right area covers the segment (24/5, 6). The middle covers the segment (2,24/5). The union of the three segments covers 5 units. So 1/6 of the collector is always dark.

0
3
1
3
Returns: "0/1"

0
0
3
4
Returns: "1/30"

1
1
3
4
Returns: "7/120"

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

Coding Area

Language: C++17 · define a public class Solar with a public method string dark(int x1, int y1, int x2, int y2) · 176 test cases · 2 s / 256 MB per case