`

【多边形重心/新增三角形叉积公式】HDU 1115 Lifting the Stone

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=1115


题意:逆时针给出n个点,求这个n边形的重心

Sample Input
2
4
5 0
0 5
-5 0
0 -5
4
1 1
11 1
11 11
1 11

Sample Output
0.00 0.00
6.00 6.00


求三角形面积公式【已知三个顶点坐标】

逆时针依次为(x1,y1),(x2,y2),(x3,y3):S为正
顺时针S为负




所谓三角形的重心就是三角形的外心,即中线交点,如图,重心坐标为(xg,yg)




求多边形重心的题目大致有这么几种:

1、质量集中在顶点上
    n个顶点坐标为(xi,yi),质量为mi,则重心
  X = ∑( xi×mi ) / ∑mi
  Y = ∑( yi×mi ) / ∑mi
  特殊地,若每个点的质量相同,则
  X = ∑xi / n
  Y = ∑yi / n

2、质量分布均匀
  特殊地,质量均匀的三角形重心:
  X = ( x0 + x1 + x2 ) / 3
  Y = ( y0 + y1 + y2 ) / 3

3、质量分布不均匀
    只能用函数多重积分来算,不太会

这题的做法:
将n边形分成多个三角形,分别求出重心坐标以及质量m【因为质量分布均匀,所以可以设密度为1,则面积就是质量】
因为质量都集中在重心
所以把所有求出来的重心按逆时针连接起来又是一个多边形
但是这个多边形的质量集中在顶点上
所以可以利用上面公式进行计算




#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;

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

double area (point a, point b, point c)    //叉积公式求三角形面积的2倍
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}

int main()
{
	int t, n, i;
	point pre;
	double gx, gy, sum, m, x1, y1;
	scanf ("%d", &t);
	while (t--)
	{
		sum = gx = gy = 0;
		scanf ("%d", &n);
		for (i = 0; i < n; i++)
			scanf ("%lf%lf", &p[i].x, &p[i].y);
		pre = p[1];
		for (i = 2; i < n; i++)
		{
			m = area (p[0], pre, p[i]);
             //设密度=2,质量=2*面积,加绝对值fabs会错,因为可能有凹边形,产生负面积...
			x1 = (p[0].x + pre.x + p[i].x) / 3;
			y1 = (p[0].y + pre.y + p[i].y) / 3;    //三角形重心坐标
			gx += m * x1;    //公式中的 ∑( xi×mi )
			gy += m * y1;    //公式中的 ∑( yi×mi )
			sum += m;    //公式中的 ∑mi
			pre = p[i];
		}
		gx /= sum, gy /= sum;
		printf ("%.2lf %.2lf\n", gx, gy);
	}
	return 0;
}
  • 大小: 27.4 KB
  • 大小: 34.5 KB
  • 大小: 33.4 KB
1
3
分享到:
评论

相关推荐

    求多边形面积、周长、重心

    对于更复杂的多边形,可能需要使用更高级的算法,如 shoelace 公式(叉积法)。 3. **周长计算**:多边形的周长是其所有边长相加的结果。遍历多边形的所有边,对每条边的长度进行累加,即可得到周长。 4. **重心...

    多边形相关算法(面积、凹凸性、凸包、两多边形相交等)

    在二维空间中,可以通过格林公式或者将多边形划分为多个三角形并累加它们的面积来实现。在VC++中,可以使用向量叉乘的方法:连接多边形的首尾顶点形成一个闭合的循环,然后对每一对相邻的顶点计算叉积,其结果的...

    三角化多边形算法(C#)

    - **向量叉积公式**: 对于两个向量A(x1, y1)和B(x2, y2),其叉积结果为A×B = x1*y2 - y1*x2。 - **凸点与凹点判断**: 如果叉积结果大于等于0,则当前顶点为凸点;如果叉积结果小于0,则当前顶点为凹点。 ##...

    C++求多边形面积的方法

    Gauss's shoelace 公式基于多边形的边界线段,通过计算每一对相邻顶点所围成的小三角形的面积并累加,最终取绝对值后除以2。这个公式的计算过程就像用鞋带穿过多边形的边界一样。以下是对应的C++代码实现: ```cpp ...

    微信小程序测量程序计算三角形多边形面积计算坐标正反算

    三角形的面积计算通常有多种方法,如海伦公式(适用于已知三边长度的情况)、底乘高除以二(适用于已知底和高的情况),以及向量叉积法(适用于已知两个顶点坐标的情况)。多边形的面积计算可以分解为多个三角形的...

    使用c++计算凸多边形的面积

    计算凸多边形面积的方法之一是使用“ shoelace公式”(也称为叉积法)。这个方法基于向量的叉积,对于每个相邻的点对 `(p_i, p_{i+1})`,我们计算这两个点所形成的向量 `(p_{i+1} - p_i)` 的叉积,然后将所有的叉积...

    计算多边形面积

    最常用的方法是将多边形的顶点按逆时针或顺时针顺序排列,然后利用叉积公式计算相邻两点之间的向量对多边形边界中心的贡献。如果顶点按照逆时针方向输入,那么正向叉积表示面积的正贡献,负向叉积表示负贡献。最后,...

    多边形面积的计算(C++实现)

    该公式基于向量代数,通过累加相邻顶点之间的叉积,再除以2,可以得到多边形的面积。公式如下: \[ \text{Area} = \frac{1}{2} |(x_1y_2 - x_2y_1) + (x_2y_3 - x_3y_2) + \cdots + (x_ny_1 - x_1y_n)| \] 其中,\...

    计算几何——三角形的相关计算

    海伦公式是基于三角形的半周长(s=(a+b+c)/2)和三边长度a、b、c来计算的,面积A=√[s(s-a)(s-b)(s-c)]。另一种常用方法是利用向量的叉积,设三角形的三个顶点为A(x1, y1), B(x2, y2), C(x3, y3),则面积A=0.5*|x1*...

    多边形面积计算器

    3. 算法:如Shoelace公式(叉积法)用于计算简单多边形的面积,通过计算所有相邻顶点的坐标叉积之和的绝对值的一半。 4. 编程语言:可以使用Python、C++、Java等编程语言实现多边形面积计算器,利用上述算法。 五、...

    Desktop_任意多边形_matlab_面积_多边形_

    Shoelace公式基于多边形的顶点坐标,通过计算每一对相邻边的叉积,然后将所有叉积相加得到面积。具体步骤如下: 1. 将多边形的顶点坐标存储为二维数组,例如 `vertices = [x1 y1; x2 y2; ... xn yn]`。 2. 初始化两...

    多边形相关题解1

    1. **多边形面积计算**:在POJ1654中,通过将多边形分割为多个三角形,利用向量叉积求得每个三角形的面积,进而求得整个多边形的面积。这种方法在处理浮点数精度问题时,使用double类型存储面积并转换为long long是...

    判断多边形点的凹凸性

    在计算机图形学中,多边形的凹凸性是一个重要的概念,它决定了多边形的形状和视觉表现。本文将深入探讨如何判断一个点在多边形中的凹凸性,并结合给定的“AnotherSolution”文件,提供可能的解决方案。 首先,我们...

    基于实验数据的多边形拓扑构建左转算法-1.zip

    在计算机图形学中,多边形的拓扑构建与左转算法是两个关键概念,尤其在二维几何处理和游戏开发中扮演着重要角色。本文将深入探讨如何利用实验数据实现多边形左转算法,以及如何自动构建多边形。 首先,让我们了解...

    Polygonal Area_C++_多边形面积计算_测绘程序_

    对于一个平面内的简单多边形(即没有自交的多边形),其面积可以通过将多边形划分为若干个三角形,然后计算这些三角形的面积并求和得到。例如,我们可以使用三角剖分方法,如耳朵剪裁算法,将多边形分割成三角形。 ...

    多边形面积计算

    首先,计算多边形面积的基础是平面几何中的“叉乘法”或“格拉斯米尔公式”。对于一个不规则多边形,可以将其划分为多个三角形,因为三角形的面积计算相对简单,即底乘高除以2。这个小工具就是基于这个思路,将...

    一个点是否在多边形中

    本篇将详细介绍如何在Android环境中判断一个点是否在多边形内部,重点讨论“点在三角形内”的算法,因为大多数多边形可以分解为多个三角形。 首先,我们要理解“点在多边形内”的定义。通常,我们采用“射线交叉法...

    求任意多边形面积 简单绘图 映射模式

    这通常通过链接最后一个顶点和第一个顶点形成一个封闭的区域,然后应用叉积公式(对于直角坐标系)或者Green's Theorem(对于极坐标系)。在VC++中,可以使用标准库如`#include &lt;vector&gt;`来存储和操作顶点,然后利用...

Global site tag (gtag.js) - Google Analytics