首页 > 代码库 > UVA 10002 Center of Masses

UVA 10002 Center of Masses

2024-07-18 21:05:55   218人阅读

题目链接：http://acm.uva.es/local/online_judge/search_uva.html

Problem:Find out the center of masses of a convex polygon.

Input:A series of convex polygons, defined as a number n ($n \le 100$) stating the number of points of the polygon, followed by n different pairs of integers (in no particular order), denoting the x and y coordinates of each point. The input is finished by a fake ``polygon" with m (m < 3) points, which should not be processed.

Output:For each polygon, a single line with the coordinates x and y of the center of masses of that polygon, rounded to three decimal digits.

解法：求多边形的重心。先求出其凸包，然后求重心。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 #define exp 1e-10 9 #define PI 3.14159265410 using namespace std;11 const int maxn=111;12 struct Point13 {14     double x,y;15     Point (double x=0,double y=0):x(x),y(y){}16     bool friend operator < (Point a,Point b)17     {18         if (a.x!=b.x) return a.x<b.x;19         return a.y<b.y;20     }21 }an[maxn],bn[maxn];22 typedef Point Vector;23 Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x , A.y+B.y); }24 Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x , A.y-B.y); }25 Vector operator * (Vector A,double p) {return Vector(A.x*p , A.y*p); }26 int dcmp(double x)27 {28     if (fabs(x)<exp) return 0;29     return x<0 ? -1 : 1;30 }31 double cross(Vector A,Vector B)32 {33     return A.x*B.y-B.x*A.y;34 }35 Point PolyGravity(Point *p,int n)36 {37     Point tmp,g=Point(0,0);38     double sumArea=0,area;39     for (int i=2 ;i<n ;i++)40     {41         area=cross(p[i-1]-p[0],p[i]-p[0]);42         sumArea += area;43         tmp.x=p[0].x+p[i-1].x+p[i].x;44         tmp.y=p[0].y+p[i-1].y+p[i].y;45         g.x += tmp.x*area;46         g.y += tmp.y*area;47     }48     g.x /= (sumArea*3.0);49     g.y /= (sumArea*3.0);50     return g;51 }52 int ConvexHull(Point *p,int n,Point *ch)53 {54     sort(p,p+n);55     int m=0;56     for (int i=0 ;i<n ;i++)57     {58         while (m>1 && dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<0) m--;59         ch[m++]=p[i];60     }61     int k=m;62     for (int i=n-2 ;i>=0 ;i--)63     {64         while (m>k && dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<0) m--;65         ch[m++]=p[i];66     }67     if (n>1) m--;68     return m;69 }70 int main()71 {72     int n;73     while (scanf("%d",&n)!=EOF)74     {75         if (n<3) break;76         for (int i=0 ;i<n ;i++)77         {78             scanf("%lf%lf",&an[i].x,&an[i].y);79         }80         int k=ConvexHull(an,n,bn);81         //cout<<"DEBUG\n";82         //for (int i=0 ;i<n ;i++) cout<<an[i].x<<" "<<an[i].y<<endl;83         Point ans=PolyGravity(bn,k);84         printf("%.3lf %.3lf\n",ans.x,ans.y);85     }86     return 0;87 }

 


联系
我们