题目链接：http://acm.uva.es/local/online_judge/search_uva.html
Problem: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.
解法：求多边形的重心。先求出其凸包，然后求重心。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 0x7fffffff
#define exp 1e-10
#define PI 3.141592654
using namespace std;
const int maxn=;
struct Point
{
double x,y;
Point (double x=,double y=):x(x),y(y){}
bool friend operator < (Point a,Point b)
{
if (a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
}an[maxn],bn[maxn];
typedef Point Vector;
Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x , A.y+B.y); }
Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x , A.y-B.y); }
Vector operator * (Vector A,double p) {return Vector(A.x*p , A.y*p); }
int dcmp(double x)
{
if (fabs(x)<exp) return ;
return x< ? - : ;
}
double cross(Vector A,Vector B)
{
return A.x*B.y-B.x*A.y;
}
Point PolyGravity(Point *p,int n)
{
Point tmp,g=Point(,);
double sumArea=,area;
for (int i= ;i<n ;i++)
{
area=cross(p[i-]-p[],p[i]-p[]);
sumArea += area;
tmp.x=p[].x+p[i-].x+p[i].x;
tmp.y=p[].y+p[i-].y+p[i].y;
g.x += tmp.x*area;
g.y += tmp.y*area;
}
g.x /= (sumArea*3.0);
g.y /= (sumArea*3.0);
return g;
}
int ConvexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=;
for (int i= ;i<n ;i++)
{
while (m> && dcmp(cross(ch[m-]-ch[m-],p[i]-ch[m-]))<) m--;
ch[m++]=p[i];
}
int k=m;
for (int i=n- ;i>= ;i--)
{
while (m>k && dcmp(cross(ch[m-]-ch[m-],p[i]-ch[m-]))<) m--;
ch[m++]=p[i];
}
if (n>) m--;
return m;
}
int main()
{
int n;
while (scanf("%d",&n)!=EOF)
{
if (n<) break;
for (int i= ;i<n ;i++)
{
scanf("%lf%lf",&an[i].x,&an[i].y);
}
int k=ConvexHull(an,n,bn);
//cout<<"DEBUG\n";
//for (int i=0 ;i<n ;i++) cout<<an[i].x<<" "<<an[i].y<<endl;
Point ans=PolyGravity(bn,k);
printf("%.3lf %.3lf\n",ans.x,ans.y);
}
return ;
}