[highlight]Solution:[/highlight]
Centroid of polygon
The centroid of a non-self-intersecting closed polygon defined by n vertices (x0,y0), (x1,y1), …, (xn−1,yn−1) is the point (Cx, Cy), where
Cx= 1/6A *sumof((X_i+X_i+1)*(X_i*Y_i+1 – X_i+1 * Y_i)); fori=0 to n-1
Cy= 1/6A *sumof((Y_i+Y_i+1)*(X_i*Y_i+1 – X_i+1 * Y_i));for i=0 to n-1
and where A is the polygon’s signed area,
A = 1/2 * sumof(X_i*Y_i+1-X_i+1*Y_i);
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <iostream> #include <algorithm> #include <vector> #include <stdio.h> using namespace std; struct point{ double x; double y; }P; vector<point> vb,vb1; int visit[1001]; bool cmp(point a,point b) { if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } int ccw(point a,point b,point c) { double p= a.x*b.y-a.x*c.y-a.y*b.x+a.y*c.x+b.x*c.y-c.x*b.y; if(p>0) return 1; else return 0; } int main() { int n; double a,b; double area,x,y; while(cin>>n) { if(n<3) break; vb.clear(); for(int i=0;i<n;i++) { cin>>a>>b; P.x=a; P.y=b; vb.push_back(P); visit[i]=0; } sort(vb.begin(),vb.end(),cmp); vb1.clear(); vb1.push_back(vb[0]); visit[0]=1; for(int i=0;i<(n-1);i++) { int next; for(int j=1;j<n;j++) { if(!visit[j]) { next=j; break; } } for(int j=1;j<n;j++) { if(visit[j]==0 && ccw(vb1[i],vb[next],vb[j])==0) next=j; } visit[next]=1; vb1.push_back(vb[next]); } vb1.push_back(vb[0]); x=0; y=0; area=0;; for(int i=0;i<n;i++) { double temp = vb1[i].x+vb1[i+1].x; double temp1=vb1[i].x*vb1[i+1].y-vb1[i].y*vb1[i+1].x; x+=double(temp*temp1); temp=vb1[i].y+vb1[i+1].y; y+=double(temp*temp1); area+=temp1; } area/=2; x=x/(area*6); y=y/(area*6); //cout<<"\n"; //for(int i=0;i<n;i++) //cout<<vb[i].x<<" "<<vb[i].y<<"\n"; printf("%.3lf %.3lf\n",x,y); } return 0; } |