Statistics

Problem Statement for "ConvexPolygon"

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 int[] x and its y-coordinate is element i of int[] y, return its exact area.

Definition

Class:
ConvexPolygon
Method:
findArea
Parameters:
int[], int[]
Returns:
double
Method signature:
double findArea(int[] x, int[] y)
(be sure your method is public)

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.

Examples

  1. {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.

  2. {-10000,-10000,10000,10000}

    {10000,-10000,-10000,10000}

    Returns: 4.0E8

    This is a 20000 x 20000 square.

  3. {-10000,-10000,10000,10000,9999}

    {10000,-10000,-10000,9999,10000}

    Returns: 3.999999995E8

  4. {-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

  5. {-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

  6. {-1917,-5248,-7825,-8658,-9670,-9783,-9926,-9961,-9956,-9910,-9828,-9471,-7591,-2798,3629,7287,7941,8380,8835,8958,9449,9985,9945,9878,9672,9513,8781,8422,8330,7097}

    {-9995,-9984,-9910,-9714,-9314,-9064,-7113,1516,6132,9297,9531,9724,9968,9984,9961,9850,9763,9685,9594,9546,9017,6477,-3759,-5631,-7598,-8175,-9760,-9905,-9918,-9991}

    Returns: 3.91427404E8

  7. {-4879,-7071,-7767,-7881,-9108,-9543,-9748,-9855,-9932,-9967,-9951,-9912,-9881,-9692,-9151,-8969,-6929,894,6930,8444,9202,9623,9951,9970,9969,9832,9551,8297,6693,4285}

    {-9927,-9789,-9741,-9709,-9077,-8080,-7352,-6779,-5946,-2781,359,5261,6473,8928,9597,9663,9899,9945,9965,9945,9616,9312,8881,-345,-6295,-8581,-9465,-9851,-9912,-9916}

    Returns: 3.89750654E8

  8. {-3074,-8275,-8428,-9055,-9411,-9451,-9681,-9873,-9983,-9998,-10000,-9898,-9843,-9760,-9355,-9196,-8779,-5939,4843,9034,9658,9937,9970,9982,9964,9928,9820,9357,7398,2999}

    {-9986,-9944,-9939,-9898,-9836,-9804,-9446,-7921,-5760,-1375,3397,7839,8365,8931,9798,9914,9933,9936,9900,9880,8759,6432,5796,4415,192,-7354,-9217,-9384,-9667,-9985}

    Returns: 3.920043245E8

  9. {987,-4328,-7688,-8815,-9130,-9650,-9813,-9891,-9951,-9977,-9916,-9793,-9536,-8883,-5392,4619,8652,9468,9678,9944,9986,9991,9997,9995,9811,9374,8905,8405,8282,5881}

    {-9997,-9993,-9978,-9795,-9380,-8574,-7354,-6246,-1534,3045,6409,8472,8957,9765,9930,9975,9758,9445,9271,8453,4693,1367,-5346,-7273,-8334,-8856,-9348,-9757,-9786,-9971}

    Returns: 3.913747745E8

  10. {2983,-8446,-9150,-9449,-9912,-9971,-9925,-9808,-9674,-9018,-8847,-5405,-2320,2748,3635,4000,4967,6849,7948,8546,9218,9783,9918,9950,9975,9989,9986,9535,9380,8432,6446}

    {-9981,-9977,-9881,-9753,-9222,-8890,4592,7769,8677,9612,9624,9789,9857,9964,9959,9954,9898,9663,9453,9289,9071,8435,8055,6123,4510,-3665,-6466,-9149,-9712,-9880,-9943}

    Returns: 3.89855996E8

  11. {-754,-3640,-7781,-8980,-9352,-9465,-9669,-9720,-9828,-9927,-9988,-9988,-9983,-9917,-9828,-9684,-8982,9023,9263,9600,9849,9888,9958,9986,9955,9871,9714,9060,8104,3894}

    {-9978,-9976,-9939,-9893,-9857,-9661,-8974,-8675,-7713,-5539,-3936,-3521,-1690,3620,8811,9454,9993,9961,9398,7537,5294,4083,-159,-5050,-6212,-7342,-8118,-9593,-9781,-9925}

    Returns: 3.9102138E8

  12. {2499,-5030,-7522,-9597,-9781,-9972,-10000,-9991,-9978,-9946,-9895,-9740,-9637,-9428,-323,4454,8504,9725,9771,9821,9967,9989,9999,9986,9980,9959,9727,9210,6478,4985}

    {-9960,-9951,-9948,-9865,-9740,-8508,514,3543,5030,5985,7066,8311,8965,9993,9972,9932,9872,9502,8932,8129,2731,1045,-560,-6334,-7554,-7892,-9760,-9890,-9943,-9955}

    Returns: 3.947343615E8

  13. {-2556,-7622,-8303,-9810,-9876,-9931,-9953,-9992,-10000,-9713,-9541,-8279,-4469,-3726,-2546,4433,8273,9612,9869,9885,9936,9947,9996,9872,9475,9105,9020,7976,6847,5180}

    {-9994,-9990,-9891,-9645,-9502,-7649,-4278,4052,8459,9439,9609,9797,9960,9977,9998,9974,9949,9567,8737,8320,6097,4965,-6980,-8055,-8964,-9527,-9591,-9918,-9952,-9982}

    Returns: 3.94283304E8

  14. {-4864,-6525,-9431,-9724,-9981,-9993,-9982,-9894,-9681,-9193,-6624,-1215,4838,7386,8503,9286,9712,9778,9792,9804,9923,9946,9990,9997,9838,9626,9338,8532,8479,3654}

    {-9998,-9988,-9856,-8917,-6329,-1683,5936,8186,9302,9896,9944,9996,9993,9946,9828,9677,9496,9425,9234,9046,6987,6117,-1243,-3688,-7672,-9161,-9465,-9929,-9932,-9986}

    Returns: 3.943907225E8

  15. {4518,-8283,-9315,-9882,-9965,-9975,-9991,-9981,-9962,-9889,-9793,-9677,-9554,-8718,-5157,-4122,2960,6235,8662,9140,9554,9796,9997,9995,9983,9930,9872,9213,8457,7853}

    {-9999,-9989,-9562,-8538,-6630,-6391,-2264,4498,6906,8010,8940,9708,9794,9924,9983,9986,9968,9954,9850,9788,9564,8928,8253,2414,-3132,-8802,-9256,-9657,-9925,-9984}

    Returns: 3.954723565E8

  16. {2203,-8160,-8805,-9152,-9699,-9734,-9912,-9971,-9986,-9998,-9987,-9691,-9413,-5108,-3942,481,7221,7958,9742,9838,9915,9993,9996,9973,9955,9885,9850,9740,9033,8151}

    {-9989,-9988,-9834,-9635,-9134,-8990,-7525,-5792,-4917,573,5724,9154,9968,9985,9988,9981,9952,9885,9226,8388,6611,4776,1399,-4483,-7700,-8679,-9115,-9676,-9898,-9971}

    Returns: 3.948633235E8

  17. {-6996,-8637,-9516,-9862,-9933,-9980,-9991,-9985,-8976,-8809,-5217,2003,7664,9101,9727,9930,9948,9996,9996,9992,9983,9976,9917,9586,9426,9389,8708,7326,850,-2340}

    {-9993,-9942,-9555,-9028,-8132,-1051,4824,7709,9792,9882,9988,9998,9995,9892,8967,7755,7582,2078,1819,-708,-5637,-7564,-8443,-9341,-9590,-9611,-9790,-9963,-9985,-9989}

    Returns: 3.94720623E8

  18. {-2622,-6046,-8427,-9373,-9517,-9681,-9829,-9895,-9950,-9994,-9997,-9993,-9976,-9950,-9863,-9756,-9624,-8212,23,5780,7816,9080,9686,9718,9890,9984,9984,9969,9891,9869,8013,3371}

    {-9995,-9991,-9963,-9934,-9917,-9802,-9489,-9264,-8261,-4628,741,4312,6512,7199,8871,9619,9871,9964,9985,9957,9908,9693,9469,9307,8374,6166,348,-4862,-8957,-9847,-9908,-9987}

    Returns: 3.961334945E8

  19. {-2849,-8983,-9628,-9544,-412,4250,5919,6654,8519,9414,9826,9776,8430,7474}

    {-9851,-8465,-7252,9316,9927,9818,9380,9105,7170,5366,1094,-1850,-6800,-9849}

    Returns: 3.556308735E8

  20. {5886,-3453,-7676,-8182,-9775,-8144,-7584,-1800,1115,4450,9353,9639,9329,8639,7304}

    {-9943,-8844,-8164,-6537,-111,6799,9142,9261,9304,8904,5603,3417,-5824,-8244,-9430}

    Returns: 3.208252885E8

  21. {-9321,-9827,-9050,-6036,4899,6815,9535,9892,9776,8652,6434}

    {-9818,4527,6779,8457,9976,9480,767,-1206,-1980,-7643,-9609}

    Returns: 3.397320645E8

  22. {-893,-8943,-9735,-9465,-6194,-77,5501,7146,8616,9330,9399,9096}

    {-9898,-9749,-723,3668,8715,9387,9990,8278,2571,-1601,-8515,-9309}

    Returns: 3.34909909E8

  23. {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)

  24. {-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.

  25. {-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.

  26. {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

  27. {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

  28. {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

  29. { -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

  30. { -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

  31. { 0, 0, 1 }

    { 0, 1, 0 }

    Returns: 0.5

  32. { 0, 0, 1 }

    { 1, 2, 1 }

    Returns: 0.5

  33. { 1, 1, -1 }

    { 1, -1, 0 }

    Returns: 2.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: