注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1115  

2012-07-17 16:54:36|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=1115

第一次做多边形重心的题,参考来自:http://www.cnblogs.com/try86/archive/2012/04/21/2462458.html

/*
摘自:KIDxの博客
求多边形重心的题目大致有这么几种:
、质量集中在顶点上
    n个顶点坐标为(xi,yi),质量为mi,则重心
  X = ∑( xi×mi ) / ∑mi
  Y = ∑( yi×mi ) / ∑mi
  特殊地,若每个点的质量相同,则
  X = ∑xi / n
  Y = ∑yi / n
、质量分布均匀
  特殊地,质量均匀的三角形重心:
  X = ( x0 + x1 + x2 ) / 3
  Y = ( y0 + y1 + y2 ) / 3
、质量分布不均匀
    只能用函数多重积分来算,不太会
这题的做法:
将n边形分成多个三角形,分别求出重心坐标以及质量m【因为质量分布均匀,所以可以设密度为1,则面积就是质量】
因为质量都集中在重心
所以把所有求出来的重心按逆时针连接起来又是一个多边形
但是这个多边形的质量集中在顶点上
所以可以利用上面公式进行计算
*/

#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;

const int N = 1000000;

struct point {
    double x;
    double y;
}p[N], g;

double crossProd(point A, point B, point C) {
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}

void compGravity(int n) {//求重心 
    point tmp;
    double sumArea, area;
    sumArea = 0;
    g.x = g.y = 0;
    for (int i=2; i<n; ++i) {
        area = crossProd(p[0], p[i-1], p[i]);
        sumArea += area;
        tmp.x = p[0].x + p[i-1].x + p[i].x;
        tmp.y = p[0].y + p[i-1].y + p[i].y;
        g.x += tmp.x * area;
        g.y += tmp.y * area;
    }
    g.x /= (sumArea * 3.0);
    g.y /= (sumArea * 3.0);
}

int main() {
    int t;
    scanf ("%d", &t);
    while (t--) {
        int n;
        scanf ("%d", &n);//顶点以逆时针方向给出 
        for (int i=0; i<n; ++i) scanf ("%lf%lf", &p[i].x, &p[i].y);
        compGravity(n);
        printf ("%.2lf %.2lf\n", g.x, g.y);
    }
    return 0;
}


  评论这张
 
阅读(201)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018