InscribedTriangles
SRM 326 · 2006-11-11 · by jmzero
Problem Statement
A triangle is "inscribed" in a circle if all 3 points of the triangle are on the edge of the circle. For this problem, our circle will be centered at the origin and have a radius of 5. Our goal is to find the largest triangle (by area) we can inscribe in this circle. Normally, this would be any equilateral triangle, but in this case we have the added restriction that each point of our triangle must be within one (or more) of the valid ranges of degrees. The degree ranges are given in thousandths of degrees in corresponding elements of angleFrom and angleTo. For each range, angleFrom will be less than or equal to angleTo and each will be between 0 and 360000. All ranges are inclusive; see the examples for clarification. Return the area of the largest inscribed triangle that can be made while following these restrictions. If no triangle can be made, return 0.
Notes
- The ranges may overlap.
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- angleFrom and angleTo will each contain between 1 and 30 elements, inclusive.
- angleFrom and angleTo will contain the same number of elements.
- Each element of angleFrom and angleTo will be between 0 and 360000, inclusive.
- Each element of angleFrom will be less than or equal to the corresponding element of angleTo.
{0,89000,180000}
{0,91000,180000}
Returns: 25.0
double constrained test. Easy to hand check this one - (radius+radius)*radius/2 = 10*5/2 = 25
{0}
{240000}
Returns: 32.47595264191645
equilateral test
{0}
{360}
Returns: 3.87577502193079E-7
note thousandths of degrees
{29829}
{29829}
Returns: 0.0
zero test
{0,30000,60000}
{0,180000,60000}
Returns: 25.0
{0,1000,2000,3000,4000,5000,6000,7000,8000,9000,
10000,11000,12000,13000,14000,15000,16000,17000,18000,19000,
20000,21000,22000,23000,24000,24999,26000,27000,28000,29000}
{1000,2000,3000,4000,5000,6000,7000,8000,9000,
10000,11000,12000,13000,14000,15000,16000,17000,18000,19000,
20000,21000,22000,23000,24000,24999,26000,27000,28000,29000,29999}
Returns: 0.22045433337735376
Best triangle can use .0005 increments (whether or not that makes a significant difference in end area)...
{15050,140055,259900}
{60045,140900,260000}
Returns: 32.47594515984052
Very, very close to an equilateral.
{0}
{360000}
Returns: 32.47595264191645
We can use any point we want on the circle - so we can draw an equilateral triangle (which will be the biggest we can ever draw).
{15000,25000,100000,265000,330000}
{15000,25000,100000,265000,330000}
Returns: 27.433829549752186
In this case, each of our ranges are single points. The biggest triangle can be made by using the points at 15°, 100°, and 265°.
{245900,246500,249900}
{245915,246611,252901}
Returns: 0.002789909594714814
We only have 3 small ranges, all near to each other - so our best triangle is still really small.
{42}
{42}
Returns: 0.0
It's hard to draw a triangle with one point.
{0}
{180000}
Returns: 25.0
Here we have just the top half of the circle to work with. The best triangle is at 0°, 90°, 180°.
{127810,122418,23013,267998,126963,287095,215811,339465,351723,318957,333732,236254,302352,335353,12935,233802,327782,281682,182002,169344,28119,108889,44436,329409,207139,305965,96162,207326,209792,302449}
{303690,284236,250009,288745,189203,346252,322811,357974,359054,327362,352355,291192,321761,344459,64616,237047,333294,302581,309236,268884,117195,312676,245636,329767,258518,326023,155880,249512,271361,317795}
Returns: 32.47595264191645
0-360 degrees
{42661,145219,87097,76231,55982,109200,24711,20792,41394,82149,164445,102096,176399,181589,83997,34423,109514,19182,173332,182443,162774,88230,62177,173717,129227,6179,7528,101197,105439,87112}
{138019,168222,176528,171293,121916,160479,113283,89752,123301,135625,183555,175807,180437,183986,123684,96872,140320,22910,174716,183934,177533,183010,137224,184258,134431,55763,43517,139773,155558,118707}
Returns: 24.577468560856083
0-185 degrees
{3630,4439,964,390,4014,3286,4147,1072,3480,3414,4642,4594,1789,2649,2872,4758,3150,3891,4961,1693,3730,2624,239,4355,4144,4405,3737,3032,1964,2373}
{4134,4679,3699,3848,4383,3718,4957,4921,4160,4916,4857,4755,2528,3399,4737,4811,4439,4031,4984,4566,4554,4004,3476,4660,4328,4909,4484,3739,3036,3794}
Returns: 8.871041458287127E-4
Small angles.
{199000,40277,40222,130,114,40236,40295,40294,40187,40245,40189,105,40198,40181,6,40154,77,40,40297,26,40289,83,122,40249,40175,91,40194,41,40207,109}
{201000,40361,40275,215,202,40312,40327,40385,40230,40264,40193,181,40298,40267,24,40154,153,72,40368,53,40348,128,177,40329,40232,187,40199,132,40256,197}
Returns: 16.72616437390915
This is built to catch ones that don't treat double-constrained case right.
{89999,280283,280235,260051,280179,260132,280216,280230,260115,260076,280195,280203,280195,260096,260008,260012,280186,280179,260136,260075,280270,280167,260050,260143,280295,280205,280167,260046,280230,280294}
{90501,280374,280313,260082,280234,260225,280268,280284,260147,260140,280201,280274,280261,260168,260060,260104,280227,280261,260195,260123,280295,280168,260057,260180,280313,280239,280196,260127,280234,280324}
Returns: 8.770015291003363
A similar double constraint
Submissions are judged against all 44 archived test cases, of which 17 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class InscribedTriangles with a public method double findLargest(vector<int> angleFrom, vector<int> angleTo) · 44 test cases · 2 s / 256 MB per case