# UVa 10002

## Summary

This problem is about finding the position of the centroid of a convex polygon.

## Explanation

Calculating the position of the centroid of a convex polygon is a basic algorithm in computational geometry. Let ${\displaystyle \{(x_{0},y_{0}),(x_{1},y_{1}),...,(x_{N-1},y_{N-1})\}}$ be the set of N vertices of a convex polygon P, where

• the Y coordinates of all vertices are nonnegative;
• ${\displaystyle (x_{0},y_{0})}$ is the leftmost vertex;
• The vertices are ordered clockwise.

We takes ${\displaystyle (x_{N},y_{N})=(x_{0},y_{0})}$. Then the area of P is ${\displaystyle {\frac {1}{2}}\sum _{i=0}^{N-1}((x_{i+1}-x_{i})(y_{i}+y_{i+1}))}$, or (in the simplified form) ${\displaystyle {\frac {1}{2}}\sum _{i=0}^{N-1}(x_{i}y_{i+1}-x_{i+1}y_{i})}$. Let A be the area of P, then the coordinates of P's centroid are ${\displaystyle x={\frac {1}{6A}}\sum _{i=0}^{N-1}((x_{i}+x_{i+1})(x_{i}y_{i+1}-x_{i+1}y_{i}))}$ and ${\displaystyle y={\frac {1}{6A}}\sum _{i=0}^{N-1}((y_{i}+y_{i+1})(x_{i}y_{i+1}-x_{i+1}y_{i}))}$.

## Gotchas

• If some of the vertices have negative Y coordinates, "shift" the polygon upwards first.
• The order of vertices from the input is randomized. So we need to find out the leftmost vertices and sort them clockwisely before applying the formulas. There are test cases with both very close points and far away points so using arctan for the sorting will not give enough precision.
• In case that there are two or more leftmost vertices, i.e. the some vertices share the minimal X coordinate, use the one with smaller Y coordinate.

• N/A

## Input

4 0 1 1 1 0 0 1 0
3 1 2 1 0 0 0
7
-4 -4
-6 -3
-4 -10
-7 -12
-9 -8
-3 -6
-8 -3
1


## Output

0.500 0.500
0.667 0.667
-6.102 -7.089


## References

1. http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/