Crane Balancing, Center of mass I am working on the ICPC 2014 Problem C "Crane Balancing"
The initial idea was to calculate the center of mass of the polygon, which I did via this equation:


Where the Area A:

Now, the solution is to binary search over the mass and look for th e maximum mass M where the crane is still balanced.
But I have a problem figuring out how the mass added affects the position of the polygon center of mass,
Thanks in advance.
 A: You have to find mass center of the whole system polygon - added mass and ensure that this center is located above polygon bottom base (without going over the extreme points)
CommonCenter.X=(PolyCenter.X*Poly.Mass + AddedMass.X*AddedMass.Mass)/(Poly.Mass+AddedMass.Mass)
CommonCenter.Y=(PolyCenter.Y*Poly.Mass + AddedMass.Y*AddedMass.Mass)/(Poly.Mass+AddedMass.Mass)

(look at A system of particles and Barycentric coordinates parts here)
A: Assume that your crane is lying on the side set L on the axis c, where L can be just a point, can be just a line section [Ai, Bi], or can be unity of points and line sections.
You don't need to know how the mass affects the crane, you just need to now the minimal and maximal mass, for which the x coordinate of the center of mass is between infinum(L) and supremum(L).
Now, just brute force for all the vertices, and for each of them find the mass that it can handle.  
And, the x coordinate of the centroid of the new system crane - lifted object, where the object is attached to the vertice (xi, yi), can be calculated by the following formula (knowing the mass of both objects):
Cx_new = Cx + (xi - Cx) * Mo/(Mc + Mo) 
Where Cx is the x coordinate of the centroid of the crane,  Mo is the mass of the object, Mc is the mass of the crane (can be calculated as Area * 1 kg/m^2).
And knowing the infinum(L) and supremum(L), you can easily find the mass that your crane can handle.
So, finding the Cx and Cy can be done in O(n), finding the MinMass and MaxMass for fixed vertice (xi, yi) can be done in O(1), and looping through all these vertices can be done in O(n), the final complexity is O(n^2).
