Smiling & Weeping

　　　　　　　　　　　　　　　　　　----繁花落尽，我心中仍有花落的声音

　　　　　　　　　　　　　　　　　　一朵，一朵，在无人的山间轻轻飘落

题目链接：1385 -- Lifting the Stone (poj.org)

思路：将多边形三角剖分，计算出每个三角形的重心，三角形的重心是顶点坐标的平均值，然后对每个三角形的有向面积求加权平均。

Talk is cheap , show me the code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdio>
 6 using namespace std;
 7 int t , n;
 8 struct Point{
 9     double x,y;
10     Point(){}
11     Point(double x , double y):x(x) , y(y){}    
12     Point operator + (Point b) {return Point(x+b.x , y+b.y); }
13     Point operator - (Point b) {return Point(x-b.x , y-b.y); }
14     Point operator * (double k) {return Point(x*k , y*k); }
15     Point operator / (double k) {return Point(x/k , y/k); }
16 }p[20010];
17 typedef Point Vector;
18 double Cross(Vector a , Vector b){
19     return a.x*b.y - a.y*b.x;
20 }
21 double Polygon_area(Point *p , int n){
22     double area=0;
23     for(int i = 0; i < n; i++)
24         area += Cross(p[i] , p[(i+1)%n]);
25     return area/2;
26 }
27 Point Polygon_center(Point *p , int n){
28     Point ans(0.0,0.0);
29     for(int i = 0; i < n; i++)
30         ans = ans + (p[i]+p[(i+1)%n])*Cross(p[i] , p[(i+1)%n]);
31     return ans/Polygon_area(p,n)/6;
32 }
33 int main()
34 {
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%d",&n);
39         for(int i = 0; i < n; i++)
40             scanf("%lf %lf",&p[i].x,&p[i].y);
41         Point ans = Polygon_center(p,n);
42         printf("%.2f %.2f\n",ans.x,ans.y);
43         // 注意尽量使用%f,兼容性好一些,G++能过
44     }
45     return 0;
46 }