hdu-1115 计算几何 求重心 凸多边形 面积
2024-09-15 02:30:28
思想是分割成三角形,然后求三角形的重心。那么多边形重心就是若干个三角形的重心带权求中心,可以用质点质心公式。
#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);
}
}
最新文章
- 2016-2017-2 《Java程序设计》课程学生博客和代码托管链接
- USACO 5.5 Picture(周长并)
- 01背包问题:Charm Bracelet (POJ 3624)(外加一个常数的优化)
- NBUT 1525 Cow Xor(01字典树+前缀思想)
- IE8一枝独秀的JS兼容BUG
- 【Java】使用Runtime执行其他程序
- gitlab 安装报错:Could not find modernizr-2.6.2 in any of the sources
- Mac软件安装提示程序已损坏解决方案
- 【原创】大数据基础之HDFS(2)HDFS副本数量检查及复制逻辑
- git将本地项目上传码云
- react + dva + ant架构后台管理系统(一)
- how2j网站前端项目——天猫前端(第一次)学习笔记5
- kepware http接口 GO语言开发
- linux 下获取文件最后几行
- Dos命令大全完整版
- hdu 5411 CRB and Puzzle (矩阵高速幂优化dp)
- 温故而知新 phpstudy 设置 nginx 代理
- ORACLE-SQL(一)
- 省队集训Day1 过河
- codeforces 357