Problem Statement
This problem takes place in a two-dimensional plane.
Everywhere in this problem the word rectangle denotes a rectangle with the following properties:
- The sides of the rectangle are parallel to the coordinate axes.
- The coordinates of the rectangle's vertices are integers between 0 and 9,999, inclusive.
- The rectangle has a positive area.
The description of a rectangle is the 4-tuple (x1, y1, x2, y2), where (x1, y1) are the coordinates of the lower left and (x2, y2) the coordinates of the upper right corner of the rectangle. I.e., (x1, y1) are the smallest and (x2, y2) the largest coordinates of a point that belongs to the rectangle.
Two rectangles are said to overlap if their intersection has a positive area.
You are given the ints N and P. Find a collection of N (not necessarily distinct) rectangles such that exactly P pairs of those rectangles intersect.
Return a int[] with 4*N elements: the concatenation of the descriptions of your N rectangles.
Definition
- Class:
- OverlappingRectangles
- Method:
- design
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] design(int N, int P)
- (be sure your method is public)
Notes
- We are counting unordered pairs of rectangles that intersect.
- You may assume that for the given constraints a solution always exists. Any valid solution will be accepted.
Constraints
- N will be between 1 and 200, inclusive.
- P will be between 0 and N * (N - 1) / 2, inclusive.
Examples
3
0
Returns: {1, 1, 2, 2, 2, 2, 4, 3, 3, 3, 7, 5 }We are supposed to return three rectangles such that no two overlap. The example return value is illustrated below. We included some pairs that touch to illustrate that this does not count as overlapping. y ^ 5 | +-------+ | | | 4 | | | | | | 3 | +-+-+-----+ | | | 2 | +-+---+ | | | 1 | +-+ | +---------------------> x 1 2 3 4 5 6 7 8 94
4
Returns: {1, 0, 101, 2, 0, 1, 2, 101, 100, 1, 102, 101, 1, 100, 101, 102 }We are looking for four rectangles such that there are four overlapping pairs. The four rectangles returned by the reference solution are {1, 0, 101, 2}, {0, 1, 2, 101}, {100, 1, 102, 101}, and {1, 100, 101, 102}. Their relative position is illustrated below. +------------+ | | +-+-+ +-+-+ | | | | | | | +-+--------+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | +-+--------+-+ | | | | | | | +-+-+ +-+-+ | | +------------+5
10
Returns: {2, 3, 4, 7, 2, 3, 4, 7, 2, 3, 4, 7, 2, 3, 4, 7, 2, 3, 4, 7 }Five rectangles, each of the ten (unordered) pairs is supposed to overlap. We simply output the same rectangle five times.