Connection Status:
Competition Arena > LotsOfLines

LotsOfLines

SRM 600 · 2013-06-25 · by ir5

SRM 600 · 2013-06-25 · by ir5 · Geometry, Math
Class Name: LotsOfLines
Return Type: long
Method Name: countDivisions
Arg Types: (int, int)
Problem Statement

Problem Statement

Note that the memory limit for all tasks in this SRM is 256 MB.

You are given ints A and B. These determine a set of A*B lines in the plane: for each pair of integers (a,b) such that 0 <= a < A and 0 <= b < B, there is a line with the equation y=ax+b.

These lines divide the plane into several regions. (Some of them are finite, some are infinite.) Compute and return the total number of regions.

Notes

  • Formally, the line with the equation y=ax+b is the set of all points (x,y) such that x is any real number and y=ax+b.

Constraints

  • A will be between 1 and 1,200, inclusive.
  • B will be between 1 and 1,200, inclusive.
Examples
0)
1
1
Returns: 2

There is only one line: y=0. This line divides the plane into two regions.

1)
2
2
Returns: 9

There are four lines. The plane looks as follows.

2)
3
2
Returns: 17
3)
1
1200
Returns: 1201

There are 1,200 horizontal lines.

4)
5
9
Returns: 638

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

Coding Area

Language: C++17 · define a public class LotsOfLines with a public method long long countDivisions(int A, int B) · 46 test cases · 2 s / 256 MB per case

Submitting as anonymous