SpriteCollision

SRM 140 · 2003-03-26 · by Yarin

Class Name: SpriteCollision

Return Type: int[]

Method Name: detect

Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)

Problem Statement

In the good old days when all games were in 2D rather than 3D, computer games often used sprites to display moving objects. A sprite is a rectangular bitmap object, whose sides are parallel with the x- and y-axis of the screen. Many systems in the eighties had special hardware circuits to display sprites on top of the background graphics. Also common was hardware which detected if two sprites collided - that is, if two sprites overlapped with each other.

Create a class SpriteCollision which contains the method detect which simulates the hardware circuit that detects if sprites collide. The method should take as input an int[] x, int[] y, int[] width and int[] height, where x[i],y[i] are the coordinates for the top-left corner of sprite i, and width[i],height[i] are the horizontal and vertical size of sprite i. The method should return an int[] containing, in increasing order, the indexes of all the sprites that overlap at least one other sprite. The first sprite has sprite index 0, etc.

Notes

If no sprites collide, return an empty int[] (see example 2).

Constraints

The number of elements in x, y, width and height are the same and between 1 and 50, inclusive.
Each element in x is between 0 and 255, inclusive.
Each element in y is between 0 and 255, inclusive.
Each element in width is between 1 and 64, inclusive.
Each element in height is between 1 and 64, inclusive.
The sum of x[i] and width[i] is between 1 and 256, inclusive.
The sum of y[i] and height[i] is between 1 and 256, inclusive.

Examples

{1,3,7,1,8,8,6,8,10,11}
{1,3,1,5,3,1,6,7,0,1}
{4,1,2,2,1,1,3,3,2,2}
{3,4,1,2,2,3,1,1,2,2}
Returns: { 0,  1,  2,  4,  5,  8,  9 }

If we plot the sprites, it will look like this: ..........88... .0000..2B.8D9.. .0000...5..99.. .00A0...C...... ...1....4...... .331........... .331..666...... ........777.... ............... '0'-'9' = Pixel occupied by a single sprite. 'A' = Pixel occupied by both sprite 0 and 1. 'B' = Pixel occupied by both sprite 2 and 5. 'C' = Pixel occupied by both sprite 4 and 5. 'D' = Pixel occupied by both sprite 8 and 9. Thus, sprite 0, 1, 2, 4, 5, 8 and 9 are all involved in collisions, so the method should return {0,1,2,4,5,8,9}.

{10,73,73}
{10,41,41}
{64,16,1}
{32,1,64}
Returns: { 0,  1,  2 }

All three sprites collide with each other at pixel 73,41.

{0,64,128,192,0,64,128,192,0,64,128,192,0,64,128,192}
{0,0,0,0,64,64,64,64,128,128,128,128,192,192,192,192}
{64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64}
{64,64,64,64,64,64,64,64,64,64,64,64,64,64,64,64}
Returns: { }

All sprites are tiled up next to each other, but there is no overlap, so the method returns {}.

{50,10,0,50,50,100,101}
{50,0,10,50,50,100,101}
{50,1,20,50,50,1,1}
{50,20,1,50,50,1,1}
Returns: { 0,  1,  2,  3,  4 }

Sprites 1 and 2 overlap, and sprites 0, 3 and 4 occupy the same pixels.

{33,144,113,162}
{166,213,181,218}
{59,32,48,46}
{36,28,9,20}
Returns: { 1,  3 }

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

Coding Area

Language: C++17 · define a public class SpriteCollision with a public method vector<int> detect(vector<int> x, vector<int> y, vector<int> width, vector<int> height) · 59 test cases · 2 s / 256 MB per case