Connection Status:
Competition Arena > OverlappingRectangles

OverlappingRectangles

TCO22 Wildcard · 2022-04-14 · by misof

TCO22 Wildcard · 2022-04-14 · by misof · Greedy, Simple Math
Class Name: OverlappingRectangles
Return Type: int[]
Method Name: design
Arg Types: (int, int)
Problem Statement

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.

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
0)
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 9

1)
4
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. +------------+ | | +-+-+ +-+-+ | | | | | | | +-+--------+-+ | | | | | | | | | | | | | | | | | | | | | | | | | | +-+--------+-+ | | | | | | | +-+-+ +-+-+ | | +------------+

2)
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.

3)
1
0
Returns: {0, 0, 2000, 1 }
4)
2
0
Returns: {0, 0, 2000, 1, 9997, 9998, 9998, 9999 }

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

Coding Area

Language: C++17 · define a public class OverlappingRectangles with a public method vector<int> design(int N, int P) · 224 test cases · 2 s / 256 MB per case

Submitting as anonymous