PerforatedSheet

SRM 235 · 2005-03-22 · by the_one_smiley

SRM 235 · 2005-03-22 · by the_one_smiley · Geometry, Math

Show categories

Class Name: PerforatedSheet

Return Type: double[]

Method Name: getCenterOfMass

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

Problem Statement

The blueprints for a large building call for a rectangular metal sheet of uniform thickness and density that has rectangular holes punched out at various positions. You are responsible for analyzing the stability of the building. To accomplish this, you need to determine the position of the perforated sheet's center of mass. The center of mass of a set of pointlike objects is defined as (Sum over all objects of object mass * object position)/(Total mass of all objects). In other words, it is the weighted average position of all the points. This definition also applies to continuous sets containing an infinite number of points, with the sum replaced by an integral and the masses replaced by a density function. For example, the center of mass of a uniformly dense rectangular sheet is just the center of the rectangle.

Write a class PerforatedSheet with a method getCenterOfMass that takes two ints sheetWidth and sheetHeight, four int[]s x, y, width, and height, and returns a double[] containing the coordinates of the perforated sheet's center of mass. If the holes consume the entire sheet (the center of mass is undefined in this case), return an empty double[]. Otherwise, return a double[] with exactly two elements, with the first equal to the x-coordinate and the second equal to the y-coordinate. The sheet is positioned with one corner at (0,0) and the opposite corner at (sheetWidth,sheetHeight). Hole i has one corner at (x[i],y[i]) and its opposite corner at (x[i]+width[i],y[i]+height[i]).

Notes

It is possible for the holes to separate the sheet into two or more disconnected pieces. The definition of center of mass still applies.
Return values with either an absolute or relative error of less than 1e-9 are considered correct.

Constraints

sheetWidth and sheetHeight will be between 1 and 2,000,000, inclusive.
x, y, width and height will each contain between 0 and 50 elements, inclusive.
x, y, width and height will contain the same number of elements.
Each element of width and height will be a positive number.
Each of the holes represented by the inputs will be within the sheet (though they may touch the edges), and none of them will overlap.

Examples

5
10
{}
{}
{}
{}
Returns: {2.5, 5.0 }

The center of mass of a uniform rectangle is just its center.

10
5
{0, 1}
{0, 0}
{1, 9}
{5, 1}
Returns: {5.5, 3.0 }

The holes here just trim the edges of the sheet, leaving a smaller rectangle.

5
5
{1}
{1}
{1}
{1}
Returns: {2.5416666666666665, 2.5416666666666665 }

Cutting out a small hole shifts the center of mass slightly.

822741
110524
{335076, 665632, 210102, 714135, 229942, 149776, 675634, 502085, 393066, 115215,
80993, 272343, 434287, 593760, 589713, 485801, 395389, 755380, 417327, 477023}
{104509, 23182, 103471, 62180, 5040, 10186, 45286, 107985, 36936, 87885,
63846, 58794, 89480, 85195, 64703, 96341, 89224, 7727, 71438, 39128}
{24578, 20552, 3332, 254, 21489, 21158, 35061, 37453, 21881, 216,
32930, 31555, 5121, 36687, 6949, 3512, 8049, 30019, 37252, 8001}
{2240, 3152, 4625, 3508, 4206, 5262, 1750, 627, 3983, 3192,
3609, 3361, 1135, 2580, 4158, 1356, 583, 5408, 5521, 2742}
Returns: {411084.49564976187, 55331.97175632337 }

1234567
314159
{0}
{0}
{1234567}
{314159}
Returns: { }

The hole consumes the entire sheet.

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

Coding Area

Language: C++17 · define a public class PerforatedSheet with a public method vector<double> getCenterOfMass(int sheetWidth, int sheetHeight, vector<int> x, vector<int> y, vector<int> width, vector<int> height) · 61 test cases · 2 s / 256 MB per case