正文

nyoj3多边形重心问题(代码片段)

GetcharZp  GetcharZp  2022-11-05  717

关键词：

多边形重心问题

时间限制：3000 ms | 内存限制：65535 KB

难度：5

描述: 　　在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接，（第一个和最后一个连接），所有线段不和其他线段相交，但是可以重合，可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形；; 　　如果是一条线段,我们定义面积为0，重心坐标为（0,0）.现在求给出的点集组成的图形的面积和重心横纵坐标的和；

输入

　　第一行有一个整数0<n<11,表示有n组数据；
　　每组数据第一行有一个整数m<10000,表示有这个多边形有m个顶点；

输出

　　输出每个多边形的面积、重心横纵坐标的和，小数点后保留三位；

样例输入

样例输出

　　0.000 0.000
　　0.500 1.000
　　0.500 1.000

/**
    注意：
        1、浮点数定义为3位输出，但输出4位的原因 -- 未加换行符 
    分析：
        1、因为n边形可以通过n个三角形组成，所以只需要计算n个三角形的面积;
        2、通过叉积公式可以计算三角形面积 S = （B-->A(x)) * (C-->A(y)） - (C-->A(x)) * (B-->A(y)),
            2.0、为了简化题目定义A为原点，S = (B(x)) * (C(y)) - (C(x)) * (B(y));
        3、三角形重心 (x)：（叉积 / 2.0） * (0 + B(x) + C(x)) / 3.0;
            3.0、三角形重心 （y） 类似与（x） 
**/

C/C++代码实现：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <stack>
#include <queue>

using namespace std;

int T, n;

double area, sum_x, sum_y, pri_1 = 0;

struct node 
    double a, b;
P[10005];

double cross_pro (int n) 
    return P[n].a * P[n + 1].b - P[n + 1].a * P[n].b;


int main () 
    scanf ("%d", &T);
    while (T --) 
        area = sum_x = sum_y = 0.0;
        scanf ("%d", &n) ;
        for (int i = 0; i < n; ++ i)
            scanf ("%lf%lf", &P[i].a, &P[i].b);
        P[n].a = P[0].a;
        P[n].b = P[0].b;
        
        for (int i = 0; i < n; ++ i) 
            double temp = cross_pro (i) / 2.0;
            area += temp;
            sum_x += temp * (P[i].a + P[i + 1].a) / 3.0;
            sum_y += temp * (P[i].b + P[i + 1].b) / 3.0;
        
        
        area = fabs (area);
        if (area <= 0.0000001) printf ("0.000 0.000\n");
        else printf ("%.3lf %.3lf\n", area, fabs ((sum_x + sum_y) / area ));
    
    return 0;

poj3855计算几何·多边形重心(代码片段)

思路：多边形面积->任选一个点，把多边形拆成三角，叉积一下三角形重心->(x1+x2+x3)/3,(y1+y2+y3)/3多边形重心公式题目中有，套一下就好了计算多边形重心方法：（1）划分多边形为三角形：以多边形的一个顶点V为源点（V... 查看详情

多边形重心，面积(代码片段)

多边形面积改革春风吹满地#include<bits/stdc++.h>usingnamespacestd;structpointdoublex,y;node[10001];doublecosr(pointa,pointb,pointc)return(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);intmain()intn;while(cin&g 查看详情

hdu1115(求质量均匀分布的多边形重心物理)(代码片段)

...逆时针方向分布的各顶点的坐标，求出n边形的重心。求多边形重心的情况大致上有三种：一、多边形的质量都分布在各顶点上，像是用轻杆连接成的多边形框，各顶点的坐标为Xi，Yi，质量为mi，则重心坐标为：　　X= ∑(xi*... 查看详情

hdu-1115（计算多边形重心）(代码片段)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1115思路：带公式：http://www.cnblogs.com/jbelial/archive/2011/08/08/2131165.html#include<iostream>#include<cstdio>#include<cmath>usingnamespac 查看详情

rotationalpainting（hdu3685凸包+多边形重心模板题(代码片段)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3685ac代码：#include<bits/stdc++.h>#definelllonglong#definemaxn50010usingnamespacestd;constdoublezero=1e-8;structnodedoublex,y;p[maxn],q[maxn];//p保存查看详情

79-多边形的面积-计算几何(代码片段)

...php?pid=3　　　　　　　　　　　　　　　　　　　　　　多边形重心问题时间限制：3000 ms | 内存限制：65535 KB难度：5 描述在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接，... 查看详情

poj1385liftingthestone多边形重心

POJ1385给定n个顶点顺序连成多边形求重心n<=1e+6比较裸的重心问题没有特别数据由于答案保留两位小数四舍五入需要+0.0005消除误差#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include& 查看详情

poj1385计算几何多边形重心

链接：http://poj.org/problem?id=1385题意：给你一个多边形，求它的重心题解：模板题，但是不知道为啥我的结果输出的确是-0.00-0.00所以我又写了个if(ans.x==0)ans.x=0感觉好傻逼代码：1#include<map>2#include<set>3#include<cmath>4#includ... 查看详情

hdu1115多边形求重心模板

1.质量集中在顶点上。n个顶点坐标为(xi,yi)，质量为mi，则重心（∑(xi×mi)/∑mi,∑(yi×mi)/∑mi)2.质量分布均匀。这个题就是这一类型，算法和上面的不同。特殊地，质量均匀的三角形重心：((x0+x1+x2)/3,Y=(y0+y1+y2)/3)以(0,0)为顶点三角剖... 查看详情

hdu1115(计算多边形几何重心)

...wproblem.php?pid=1115 题意：给出一些点，求这些点围成的多边形的重心；思路：方法1：直接分别求所有点的x坐标的平均值和y坐标的平均值，即答案；不过这个方法的计算精度不是很高，要求高精度时用另一个方法；方... 查看详情

计算几何常用的函数/方法(代码片段)

(一)求多边形的面积（用叉积计算）代码如下：1//叉积,可以用来判断方向和求面积23doublecross(Pointa,Pointb,Pointc)45return(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);678910111213//求多边形的面积1415doubleS(Pointp[],intn)1617doubleans=0;1819p[n]=p[0];2021for(inti=1;i&l... 查看详情

[考试反思]0209省选模拟22：谬误(代码片段)

...。 T1：遮天蔽日大意：点光源照圆，中间有个不透明多边形，多边形会绕重心自转，绕圆形公转，给定时刻，求圆被照射到的弧长。题目的本意是好的，但是写起来是真的恶心。看着$std$大概写了下来，其实很好理解，也并... 查看详情

bzoj4603平凡的骰子(代码片段)

题目大意：思路：首先我们需要求出整个凸多面体的重心可以通过把多面体剖分为四面体求出每个四面体的重心四面体的重心为四个点的坐标和/4对每个四面体的重心加上它们体积的权加权平均数即为整个的重心（求每个四... 查看详情

hdu1115liftingthestone（几何，求多边形重心模板题）

转载请注明出处：http://blog.csdn.net/u012860063题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1115LiftingtheStoneProblemDescriptionTherearemanysecretopeningsinthefloorwhicharecoveredbyabigheavystone.Whenthest 查看详情

树的重心(代码片段)

定义对于一颗n个节点的无根树，找到一个点，使得把树变成以该节点为根的有根树时，最大节点数最少。换句话说，删除这个节点后最大连通块（一定是树）的节点数最少。分析该问题跟树的最大独立集问题类似。先任选一个... 查看详情

opencv⚠️高手勿入!半小时学会基本操作15⚠️对象测量(代码片段)

...手勿入!半小时学会基本操作15⚠️对象测量概述对象测量多边形拟合计算对象中心概述OpenCV是一个跨平台的计算机视觉库,支持多语言,功能强大.今天小白就带大家一起携手走进OpenCV的世界.(第15课)对象测量对象测量可以帮助我们... 查看详情

求树的重心(代码片段)

给定一棵树,求树的重心的编号以及重心删除后得到的最大子树的节点个数size,如果size相同就选取编号最小的.首先要知道什么是树的重心,树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树... 查看详情

题解luogu5666树的重心(代码片段)

...粗……----思路分析很容易想到$O(n^2)$每次暴力找重心，这个暴力可以用各种神仙方法优化。通过分析35分的特殊构造分，可以有一个想法，既然特殊构造可以有结论，那么是否也可以有一些结论来解决或者优化整个问题的... 查看详情