UVa 10002

From Algorithmist

Contents 1 10002 - Center of Masses 2 Summary 3 Explanation 4 Gotchas 5 Notes 6 Input 7 Output 8 References

[edit] 10002 - Center of Masses

• http://acm.uva.es/p/v100/10002.html

[edit] Summary

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

[edit] Explanation

Calculating the position of the centroid of a convex polygon is a basic algorithm in computational geometry. Let {(x₀,y₀),(x₁,y₁),...,(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;
• (x₀,y₀) is the leftmost vertex;
• The vertices are ordered clockwise.

We takes (x_N,y_N) = (x₀,y₀). 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 .

[edit] 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.
• In case that there are two leftmost vertices, i.e. the two vertices have the same X coordinate, use the one with smaller Y coordinate.

[edit] Notes

• N/A

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

[edit] Output

0.500 0.500
0.667 0.667
-6.102 -7.089

[edit] References

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