#include <iostream>
#include <cmath>
#include<fstream>
using namespace std;
struct Point
{
float x,y;
};
float multiply(Point p1,Point p2,Point p0)
{
return((p1.x-p0.x)*(p2.y-p0.y)-(p2.
x-p0.x)*(p1.y-p0.y));
}
float dis(Point p1,Point p2)
{
return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
void Graham_scan(Point PointSet[],Point ch[],int n,float &len)
{
int i,j,k=0,top=2;
Point tmp;
for(i=1;i<n;i++)
if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))
k=i;
tmp=PointSet[0];
PointSet[0]=PointSet[k];
PointSet[k]=tmp;
for (i=1;i<n-1;i++)
{
k=i;
for (j=i+1;j<n;j++)
if( (multiply(PointSet[j],PointSet[k],PointSet[0])>0)
||((multiply(PointSet[j],PointSet[k],PointSet[0])==0)
&&(dis(PointSet[0],PointSet[j])<dis(PointSet[0],PointSet[k]))) )
k=j;
tmp=PointSet[i];
PointSet[i]=PointSet[k];
PointSet[k]=tmp;
}
ch[0]=PointSet[0];
ch[1]=PointSet[1];
ch[2]=PointSet[2];
for (i=3;i<n;i++)
{
while(multiply(PointSet[i],ch[top],ch[top-1])>=0)
top--;
ch[++top]=PointSet[i];
}
len=top+1;
}
const int maxN=1000;
Point PointSet[maxN];
Point ch[maxN];
float len;
int i;
int sumx,sumy;
int main()
{
const int n=41;
float zhongx,zhongy;
ifstream infile("polygon.txt");
for(i=0;i<n;i++)
{infile>>PointSet[i].x>>PointSet[i].y;}
infile.close();
Graham_scan(PointSet,ch,n,len);
ofstream outfile("tubao.txt");
for(i=0;i<len;i++)
{outfile<<ch[i].x<<" "<<ch[i].y<<endl;
sumx+=ch[i].x,sumy+=ch[i].y;}
zhongx=sumx/(len),zhongy=sumy/(len);
cout<<"最小凸包的几何中心为："<<"("<<zhongx<<" "<<zhongy<<")"<<endl;
return 0;
}
