思想是分割成三角形,然后求三角形的重心。那么多边形重心就是若干个三角形的重心带权求中心,可以用质点质心公式。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define LL int
const LL mod=;
const LL N=;
LL dp[N];
LL bit[];
using namespace std; struct Point
{
double x,y;
};//约定传入点的vector包含n+1个点,最后一个点与第一个点等值(模拟闭合圈)
int n;
double Area(vector<Point> va)
{
double rec=;
for(int i=;i<va.size()-;i++)
rec+=va[i].x*va[i+].y-va[i+].x*va[i].y;
rec*=0.5;
return rec;
}
Point GrvCenter(vector<Point> va)
{
Point rec;
rec.x=,rec.y=;
double area=Area(va);//每个三角形在总面积中的权重
for(int i=;i<va.size()-;i++)
rec.x+=(va[i].x+va[i+].x)*(va[i].x*va[i+].y-va[i+].x*va[i].y);
for(int i=;i<va.size()-;i++)
rec.y+=(va[i].y+va[i+].y)*(va[i].x*va[i+].y-va[i+].x*va[i].y);
rec.x/=area*;
rec.y/=area*;
return rec;
}
int main()
{
cin.sync_with_stdio(false);
int t;
int n;
scanf("%d",&t);
while(t--)
{
vector<Point> va;
scanf("%d",&n);
for(int i=;i<n;i++)
{
Point x;
scanf("%lf %lf",&x.x,&x.y);
va.push_back(x);
}
va.push_back(*va.begin());
printf("%.2f %.2f\n",GrvCenter(va).x,GrvCenter(va).y);
}
}

最新文章

  1. 2016-2017-2 《Java程序设计》课程学生博客和代码托管链接
  2. USACO 5.5 Picture(周长并)
  3. 01背包问题:Charm Bracelet (POJ 3624)(外加一个常数的优化)
  4. NBUT 1525 Cow Xor(01字典树+前缀思想)
  5. IE8一枝独秀的JS兼容BUG
  6. 【Java】使用Runtime执行其他程序
  7. gitlab 安装报错:Could not find modernizr-2.6.2 in any of the sources
  8. Mac软件安装提示程序已损坏解决方案
  9. 【原创】大数据基础之HDFS(2)HDFS副本数量检查及复制逻辑
  10. git将本地项目上传码云
  11. react + dva + ant架构后台管理系统(一)
  12. how2j网站前端项目——天猫前端(第一次)学习笔记5
  13. kepware http接口 GO语言开发
  14. linux 下获取文件最后几行
  15. Dos命令大全完整版
  16. hdu 5411 CRB and Puzzle (矩阵高速幂优化dp)
  17. 温故而知新 phpstudy 设置 nginx 代理
  18. ORACLE-SQL(一)
  19. 省队集训Day1 过河
  20. codeforces 357

热门文章

  1. CXF整合spring,在tomcat中发布webService
  2. Bootstrap3基础 navbar 导航条 简单示例
  3. p3396 哈希冲突(暴力)
  4. 使用closest替换parent
  5. URAL 1004 Sightseeing Trip(floyd求最小环+路径输出)
  6. SVN的常用功能使用教程
  7. python-ConfigParser模块【读写配置文件】
  8. 关于set和map迭代器支持的运算
  9. 理解 Redis(2) - 手把手教你理清 Redis 安装全过程
  10. yum节省安装时间