UVa 10002

From Algorithmist
Jump to navigation Jump to search

10002 - Center of Masses[edit]

Summary[edit]

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

Explanation[edit]

Calculating the position of the centroid of a convex polygon is a basic algorithm in computational geometry. Let be the set of N vertices of a convex polygon P, where

  • the Y coordinates of all vertices are nonnegative;
  • is the leftmost vertex;
  • The vertices are ordered clockwise.

We takes . Then the area of P is , or (in the simplified form) . Let A be the area of P, then the coordinates of P's centroid are and .

Gotchas[edit]

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

Notes[edit]

  • N/A

Input[edit]

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[edit]

0.500 0.500
0.667 0.667
-6.102 -7.089

References[edit]

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