poj 1385 Lifting the Stone (多边形的重心)

  1#include <cstdio>
  2#include <cstring>
  3#include <iostream>
  4#include <algorithm>
  5#include <vector>
  6#include <queue>
  7#include <set>
  8#include <map>
  9#include <string>
 10#include <cmath>
 11#include <cstdlib>
 12#include <ctime>
 13#define fst first
 14#define sec second
 15#define lson l,m,rt<<1
 16#define rson m+1,r,rt<<1|1
 17#define ms(a,x) memset(a,x,sizeof(a))
 18typedef long long LL;
 19#define pi pair < int ,int >
 20#define MP make_pair
 21using namespace std;
 22const double eps = 1E-8;
 23const int dx4[4]={1,0,0,-1};
 24const int dy4[4]={0,-1,1,0};
 25const int inf = 0x3f3f3f3f;
 26const int N=1E6+7;
 27int dblcmp(double d)
 28{
 29    return d < -eps ? -1 : d > eps;
 30}
 31struct point
 32{
 33    double x,y;
 34    point(){}
 35    point(double _x,double _y):
 36    x(_x),y(_y){};
 37    void input()
 38    {
 39        scanf("%lf%lf",&x,&y);
 40    }
 41    void output()
 42    {
 43	if (dblcmp(x)==0) x = 0;
 44	if (dblcmp(y)==0) y = 0;
 45        printf("%.2f %.2f\n",x,y);
 46    }
 47    point sub(point p)
 48    {
 49        return point(x-p.x,y-p.y);
 50    }
 51    point div(double b)
 52    {
 53        return point(x/b,y/b);
 54    }
 55    double dot(point p)
 56    {
 57        return x*p.x+y*p.y;
 58    }
 59    double det(point p)
 60    {
 61        return x*p.y-y*p.x;
 62    }
 63}p[N],ans;
 64struct polygon
 65{
 66    int n ;
 67    void input()
 68    {
 69	for ( int i = 0 ; i < n ; i++) p[i].input();
 70    }
 71    point getbarycentre()
 72    {
 73        point ret(0,0);
 74        double area=0;
 75        int i;
 76        for (i=1;i<n-1;i++)
 77        {
 78            double tmp=p[i].sub(p[0]).det(p[i+1].sub(p[0]));
 79            if (dblcmp(tmp)==0)continue;
 80            area+=tmp;
 81            ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;
 82            ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;
 83        }
 84        if (dblcmp(area))ret=ret.div(area);
 85        return ret;
 86    }
 87}pol;
 88int main()
 89{
 90	#ifndef  ONLINE_JUDGE 
 91	freopen("code/in.txt","r",stdin);
 92  #endif
 93	int T;
 94	int n ;
 95	cin>>T;
 96	while (T--)
 97	{
 98	  //  ms(p,0);
 99	    scanf("%d",&n);
100	    pol.n = n ;
101	    pol.input();
102	    ans = pol.getbarycentre();
103	    ans.output();
104	}
105  #ifndef ONLINE_JUDGE  
106  fclose(stdin);
107  #endif
108    return 0;
109}