ConvexPolygon
SRM 166 · 2003-10-01 · by dimkadimon
Problem Statement
A convex polygon is a set of n vertices that are joined by n edges, such that no two edges intersect and all angles are less than 180 degrees. We can represent a polygon by listing all the vertices, starting at one vertex and following the edges until that vertex is reached again. Thus, element 0 in the array represents the first vertex. The first vertex is connected to the second vertex (element 1), the second vertex is connected to the third vertex (element 2) and so on. The last element represents the last vertex, which is connected to the first vertex.
Given the vertices of a polygon, where the x-coordinate of vertex i is element i of
Notes
- As long as your return has relative or absolute error less than 1e-9, it will be judged correct.
Constraints
- x and y will have the same number of elements.
- x will have between 3 and 50 elements inclusive.
- y will have between 3 and 50 elements inclusive.
- each element in x will be between -10000 and 10000 inclusive.
- each element in y will be between -10000 and 10000 inclusive.
- the represented polygon will NOT intersect itself.
- the represented polygon will NOT have any angles equal to or greater than 180 degrees.
{0,0,1}
{0,1,0}
Returns: 0.5
This polygon is a right triangle with two sides of length 1. Its exact area is 0.5.
{-10000,-10000,10000,10000}
{10000,-10000,-10000,10000}
Returns: 4.0E8
This is a 20000 x 20000 square.
{-10000,-10000,10000,10000,9999}
{10000,-10000,-10000,9999,10000}
Returns: 3.999999995E8
{-4139,-8591,-9184,-9743,-9840,-9912,-9944,-9974,-9979,-9994,-9997,-9998,-10000,-10000,-9999,-9998,-9997,-9990,-9882,-9488,-9241,-2353,710,7121,7509,9871,9888,9934,9967,9990,9995,9998,9999,10000,9996,9993,9953,9890,9848,9513,9095}
{-9999,-9995,-9979,-9948,-9891,-9655,-9512,-9291,-9182,-7776,-7422,-5036,3523,4185,6835,8198,9193,9684,9953,9990,9999,10000,10000,9995,9994,9981,9979,9890,9734,9550,9505,9244,7732,-4496,-8321,-9676,-9812,-9927,-9935,-9996,-9999}
Returns: 3.996549835E8
{-3803,-6043,-7954,-8510,-9469,-9911,-9963,-9994,-9997,-10000,-10000,-9999,-9981,-9976,-9920,-9860,-9799,-9643,-9539,-8028,-6925,-5483,1837,4918,9644,9701,9772,9914,9976,9993,9997,9998,9998,9997,9988,9931,9853,9790,9697,9472,7142}
{-10000,-9999,-9997,-9993,-9974,-9960,-9911,-9578,-9305,-5960,-2177,7639,8665,8839,9413,9894,9925,9959,9964,9984,9993,10000,10000,9999,9993,9975,9945,9840,9743,9008,6329,-954,-4733,-8886,-9120,-9458,-9799,-9959,-9983,-9997,-10000}
Returns: 3.99532343E8
{100,80,30,-30,-80,-100,-80,-30,30,80}
{0,58,95,95,58,0,-58,-95,-95,-58}
Returns: 29020.0
Regular decagon with radius 100 and centre at (0,0)
{-1646,-9172,-9830,-9802,-9749,-9474,-8668,-6832,120,8380,9338,9307,8042}
{-9998,-8619,-7863,3976,4541,5975,8127,9500,9612,8734,5216,-9042,-9689}
Returns: 3.55115104E8
Random polygon.
{-6010,-7937,-8782,-9506,-9654,-9852,-9854,-9998,-9999,-9996,-9901,-9811,
-9444,-8798,-8580,-2085,6842,8339,9827,9946,9993,9959,9940,9855,9657,
8504,8262,7552,6326,5537,4723}
{-9976,-9947,-9873,-9739,-9654,-8501,-8475,-5009,475,4926,7078,8673,9417,
9785,9820,9974,9986,9979,9862,9211,-5070,-6599,-7121,-8624,-8912,-9710,
-9766,-9863,-9914,-9941,-9962}
Returns: 3.939960635E8
Another random polygon.
{100,99,96,92,87,80,72,63,53,42,30,18,6,-6,-18,-30,-42,-53,-63,-72,-80,-87,-92,-96,-99,-100,-99,-96,-92,-87,-80,-72,-63,-53,-42,-30,-18,-6,6,18,30,42,53,63,72,80,87,92,96,99}
{0,12,24,36,48,58,68,77,84,90,95,98,99,99,98,95,90,84,77,68,58,48,36,24,12,0,-12,-24,-36,-48,-58,-68,-77,-84,-90,-95,-98,-99,-99,-98,-95,-90,-84,-77,-68,-58,-48,-36,-24,-12}
Returns: 30894.0
50gon radius 100
{10000,9921,9685,9297,8763,8090,7289,6374,5358,4257,3090,1873,627,-627,-1873,-3090,-4257,-5358,-6374,-7289,-8090,-8763,-9297,-9685,-9921,-10000,-9921,-9685,-9297,-8763,-8090,-7289,-6374,-5358,-4257,-3090,-1873,-627,627,1873,3090,4257,5358,6374,7289,8090,8763,9297,9685,9921}
{0,1253,2486,3681,4817,5877,6845,7705,8443,9048,9510,9822,9980,9980,9822,9510,9048,8443,7705,6845,5877,4817,3681,2486,1253,0,-1253,-2486,-3681,-4817,-5877,-6845,-7705,-8443,-9048,-9510,-9822,-9980,-9980,-9822,-9510,-9048,-8443,-7705,-6845,-5877,-4817,-3681,-2486,-1253}
Returns: 3.13298308E8
50gon radius 10000
{10000,9917,9672,9269,8713,8014,7183,6234,5183,4047,2845,1595,320,-960,-2225,-3453,-4625,-5721,-6723,-7614,-8380,-9009,-9490,-9815,-9979,-9979,-9815,-9490,-9009,-8380,-7614,-6723,-5721,-4625,-3453,-2225,-960,320,1595,2845,4047,5183,6234,7183,8014,8713,9269,9672,9917}
{0,1278,2536,3752,4907,5981,6956,7818,8551,9144,9586,9871,9994,9953,9749,9384,8865,8201,7402,6482,5455,4338,3151,1911,640,-640,-1911,-3151,-4338,-5455,-6482,-7402,-8201,-8865,-9384,-9749,-9953,-9994,-9871,-9586,-9144,-8551,-7818,-6956,-5981,-4907,-3752,-2536,-1278}
Returns: 3.13255571E8
49gon radius 10000
Submissions are judged against all 33 archived test cases, of which 11 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConvexPolygon with a public method double findArea(vector<int> x, vector<int> y) · 33 test cases · 2 s / 256 MB per case