ConvexPolygon | Topcoder Archive

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

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

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

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.