CultureGrowth
SRM 249 · 2005-06-29 · by AdminBrett
SRM 249 · 2005-06-29 · by AdminBrett · Geometry
Problem Statement
Problem Statement
You are analyzing the behavior of an organism with peculiar growth patterns. Initially, you have placed the organisms at various spots in a rectangular tray. To precisely measure where each organism is, you have overlaid the tray with a Cartesian coordinate system.
The initial state will be described inint[] s xs and ys. Organism i is located at coordinates (xs[i],ys[i]). You have noticed that if organisms are present at (x1,y1) and (x2,y2) then shortly afterward, there will also be an organism at ( (x1+x2)/2 , (y1+y2)/2 ). There is no truncation in this operation, so organisms can occur at non-integral coordinates. As far as you are concerned, the organisms are each points, and the process has been allowed to run until completion.
You feel that an accurate measure of the final number of organisms is the area they cover. Return this area.
The initial state will be described in
You feel that an accurate measure of the final number of organisms is the area they cover. Return this area.
Notes
- Return values must be accurate to 1e-9, relative or absolute.
- To be mathematically precise, we assume that each organism takes up some small amount of area.
Constraints
- xs will contain between 1 and 50 elements inclusive.
- ys will contain the same number of elements as xs.
- Each element of xs and ys will be between 0 and 10000 inclusive.
- Every point (xs[i],ys[i]) will be distinct.
Examples
0)
{0, 3}
{0, 3}
Returns: 0.0
1)
{0, 0, 3, 3}
{0, 3, 3, 0}
Returns: 9.0
2)
{0, 0, 3, 3, 1, 2}
{0, 3, 3, 0, 1, 2}
Returns: 9.0
3)
{0, 0, 0, 1, 2, 3, 4, 4, 4, 3, 2, 1, 1, 2}
{10, 20, 30, 40 , 50, 60, 70, 30, 10, 8, 6, 8, 30, 30}
Returns: 168.0
4)
{0, 3, 6, 10}
{0, 3, 6, 10}
Returns: 0.0
The organisms are all in a line.
6)
{10}
{240}
Returns: 0.0
Only a single organism.
Submissions are judged against all 57 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CultureGrowth with a public method double finalTray(vector<int> xs, vector<int> ys) · 57 test cases · 2 s / 256 MB per case