首页 > 代码库 > UVALive 4426 Blast the Enemy! --求多边形重心
UVALive 4426 Blast the Enemy! --求多边形重心
题意：求一个不规则简单多边形的重心。
解法：多边形的重心就是所有三角形的重心对面积的加权平均数.
关于求多边形重心的文章： 求多边形重心
用叉积搞一搞就行了。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 1000000007#define eps 1e-8using namespace std;struct Point{ double x,y; Point(double x=0, double y=0):x(x),y(y) {} void input() { scanf("%lf%lf",&x,&y); }};typedef Point Vector;int dcmp(double x) { if(x < -eps) return -1; if(x > eps) return 1; return 0;}Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }double CalcConvexArea(Point* p,int n) { //凸包面积 double area = 0.0; for(int i=1;i<n-1;i++) area += Cross(p[i]-p[0],p[i+1]-p[0]); return area*0.5;}Point p[106],ch[106];int main(){ int n,i,j,cs = 1; while(scanf("%d",&n)!=EOF && n) { for(i=0;i<n;i++) p[i].input(); double S = CalcConvexArea(p,n); double X = 0.0, Y = 0.0; for(i=2;i<n;i++) { double area = 0.5*Cross(p[i-1]-p[0],p[i]-p[0]); X += area*(p[0].x+p[i-1].x+p[i].x)/3.0; Y += area*(p[0].y+p[i-1].y+p[i].y)/3.0; } printf("Stage #%d: %.6f %.6f\n",cs++,X/S,Y/S); } return 0;}
UVALive 4426 Blast the Enemy! --求多边形重心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。