Center of Masses

Find out the center of masses of a convex polygon.

Input 

A series of convex polygons, defined as a number n () stating the number of points of the polygon, followed by n different pairs of integers (in no particular order), denoting the x and y coordinates of each point. The input is finished by a fake ``polygon" with m (m < 3) points, which should not be processed.

Output 

For each polygon, a single line with the coordinates x and y of the center of masses of that polygon, rounded to three decimal digits.

Sample 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

Sample Output 

0.500 0.500
0.667 0.667
-6.102 -7.089

---

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Point {
    int x, y;
};
Point P[200], CH[200];
int cmp(const void *i, const void *j) {
    Point *x, *y;
    x = (Point *)i, y = (Point *)j;
    if(x->x != y->x)
        return x->x - y->x;
    return x->y - y->y;
}
int cross(Point *o, Point *a, Point *b) {
    return (o->x - a->x)*(o->y - b->y) -
            (o->y - a->y)*(o->x - b->x);
}
void centerOfMass(int n) {
    double cx, cy, nx, ny;
    double area1 = 0, area2;
    int i;
    cx = (CH[0].x+CH[1].x+CH[2].x)/3.0;
    cy = (CH[0].y+CH[1].y+CH[2].y)/3.0;
    area1 = cross(&CH[0], &CH[1], &CH[2])/2.0;

    for(i = 3; i < n-1; i++) {
        area2 = cross(&CH[0], &CH[i-1], &CH[i])/2.0;
        nx = (CH[0].x+CH[i-1].x+CH[i].x)/3.0;
        ny = (CH[0].y+CH[i-1].y+CH[i].y)/3.0;
        cx = cx + (nx-cx)*(area2)/(area1+area2);
        cy = cy + (ny-cy)*(area2)/(area1+area2);
        area1 += area2;
    }
    printf("%.3lf %.3lf\n", cx, cy);
}
void convexHull(int n) {
    qsort(P, n, sizeof(Point), cmp);
    int m = 0, t, i;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(&CH[m-2], &CH[m-1], &P[i]) <= 0)
            m--;
        CH[m++] = P[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(&CH[m-2], &CH[m-1], &P[i]) <= 0)
            m--;
        CH[m++] = P[i];
    }
    if(m >= 4)
        centerOfMass(m);
}
inline int readchar() {
    const int N = 131072;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n;
    while(ReadInt(&n)) {
        if(n < 3)
            continue;
        for(int i = 0; i < n; i++) {
            ReadInt(&P[i].x);
            ReadInt(&P[i].y);
        }
        convexHull(n);
    }
    return 0;
}