10002

[highlight]Solution:[/highlight]
Centroid of polygon

The centroid of a non-self-intersecting closed polygon defined by n vertices (x0,y0), (x1,y1), …, (xn−1,yn−1) is the point (Cx, Cy), where

Cx= 1/6A *sumof((X_i+X_i+1)*(X_i*Y_i+1 – X_i+1 * Y_i)); fori=0 to n-1

Cy= 1/6A *sumof((Y_i+Y_i+1)*(X_i*Y_i+1 – X_i+1 * Y_i));for i=0 to n-1

and where A is the polygon’s signed area,

A = 1/2 * sumof(X_i*Y_i+1-X_i+1*Y_i);

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

struct point{
double x;
double y;
}P;

vector<point> vb,vb1;
int visit[1001];

bool cmp(point a,point b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}

int ccw(point a,point b,point c)
{
double p= a.x*b.y-a.x*c.y-a.y*b.x+a.y*c.x+b.x*c.y-c.x*b.y;
if(p>0)
return 1;
else
return 0;
}

int main()
{
int n;
double a,b;
double area,x,y;
while(cin>>n)
{
if(n<3)
break;
vb.clear();
for(int i=0;i<n;i++)
{
cin>>a>>b;
P.x=a;
P.y=b;
vb.push_back(P);
visit[i]=0;
}

sort(vb.begin(),vb.end(),cmp);

vb1.clear();

vb1.push_back(vb[0]);
visit[0]=1;
for(int i=0;i<(n-1);i++)
{
int next;
for(int j=1;j<n;j++)
{
if(!visit[j])
{
next=j;
break;
}
}

for(int j=1;j<n;j++)
{
if(visit[j]==0 && ccw(vb1[i],vb[next],vb[j])==0)
next=j;
}
visit[next]=1;
vb1.push_back(vb[next]);

}
vb1.push_back(vb[0]);
x=0;
y=0;
area=0;;
for(int i=0;i<n;i++)
{
double temp = vb1[i].x+vb1[i+1].x;
double temp1=vb1[i].x*vb1[i+1].y-vb1[i].y*vb1[i+1].x;

x+=double(temp*temp1);
temp=vb1[i].y+vb1[i+1].y;
y+=double(temp*temp1);
area+=temp1;
}
area/=2;

x=x/(area*6);
y=y/(area*6);
//cout<<"\n";
//for(int i=0;i<n;i++)
//cout<<vb[i].x<<" "<<vb[i].y<<"\n";
printf("%.3lf %.3lf\n",x,y);
}

return 0;
}