UVA10002求凸包的质心

  1 /*UVA10002
  2 求凸包的质心，而且这道题并没有说明是否按照顺序排序，还是最好求一下凸包
  3 注意结构体的构造函数赋初值的问题
  4 ps：整理模板
  5 */
  6 #include <stdio.h>
  7 #include <stdlib.h>
  8 #include <string.h>
  9 #include <math.h>
 10 #include <ctype.h>
 11 #include <string>
 12 #include <iostream>
 13 #include <sstream>
 14 #include <vector>
 15 #include <queue>
 16 #include <stack>
 17 #include <map>
 18 #include <list>
 19 #include <set>
 20 #include <algorithm>
 21 #define eps 1e-10
 22 #define maxn 100+10
 23 
 24 using namespace std;
 25 
 26 struct Point
 27 {
 28     double x,y;
 29     Point(){}
 30     Point(double xx,double yy){x=xx,y=yy;}
 31     bool operator < (const Point& p)const{
 32         return (x<p.x || (fabs(x-p.x)<eps && y<p.y));
 33     }
 34 } P1[maxn],P2[maxn];
 35 
 36 
 37 typedef Point Vector;
 38 Vector operator - (Vector A, Vector B)
 39 {
 40     return (Vector){A.x-B.x, A.y-B.y};
 41 }
 42 double Cross(Vector A, Vector B)
 43 {
 44     return A.x*B.y - A.y*B.x;
 45 }
 46 int ConvexHull(Point *p, int n, Point* ch) //求凸包
 47 {
 48     sort(p, p + n);//先按照 x，再按照 y
 49     int m = 0;
 50     for(int i = 0; i < n; i++)
 51     {
 52         while(m > 1 && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
 53         ch[m++] = p[i];
 54     }
 55     int k = m;
 56     for(int i = n-2; i >= 0; i--)
 57     {
 58         while(m > k && Cross(ch[m-1] - ch[m-2], p[i] - ch[m-2]) <= 0) m--;
 59         ch[m++] = p[i];
 60     }
 61     if(n > 1) m--;
 62     return m;
 63 }
 64 Point BaryCenter(Point p[], int n){
 65     Point ret=Point(0,0);//因为构造函数的关系，记得结构体也要清零
 66     double area = 0;
 67     for(int i = 1; i < n; i++){
 68         double area2 = Cross(p[i-1], p[i]);     //上下都取面积的2倍，最后会被约掉的
 69         ret.x += (p[i-1].x + p[i].x) / 3 * area2;
 70         ret.y += (p[i-1].y + p[i].y) / 3 * area2;
 71         area += area2;
 72     }
 73     double area2 = Cross(p[n-1], p[0]);
 74     ret.x += (p[n-1].x + p[0].x) / 3 * area2;
 75     ret.y += (p[n-1].y + p[0].y) / 3 * area2;
 76     area += area2;
 77     ret.x /= area;
 78     ret.y /= area;
 79     return ret;
 80 }
 81 int n1,n2;
 82 int main()
 83 {
 84     while(scanf("%d",&n1)!=EOF)
 85     {
 86         if (n1<3) break;
 87         for(int i=0; i<n1; i++)
 88         {
 89             int x,y;
 90             cin>>x>>y;
 91             P1[i].x=(double)x;
 92             P1[i].y=(double)y;
 93         }
 94         n2=ConvexHull(P1,n1,P2);
 95         Point ans=BaryCenter(P2,n2);
 96         double x=ans.x,y=ans.y;
 97         printf("%.3lf %.3lf
",x,y);
 98     }
 99     return 0;
100 }