多边形重心问题

Dear 丶 2022-08-11 16:54 208阅读 0赞

描述

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

输入

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

输出

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

样例输入

3
    3
    0 1
    0 2
    0 3
    3
    1 1
    0 0
    0 1
    4
    1 1
    0 0
    0 0.5
    0 1

样例输出

0.000 0.000
    0.500 1.000
    0.500 1.000

#include <stdio.h>
    #include <math.h>
    inline double g(double x1, double y1, double x2, double y2, double x3,
    		double y3) {
    	return (x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2;
    }
    int main() {
    	int n, m;
    	scanf("%i", &n);
    	while (n--) {
    		scanf("%i", &m);
    		m -= 2;
    		double x1, y1, x, y, xn, yn, gsx = 0, gsy = 0, s = 0, cs = 0;
    		scanf("%lf%lf%lf%lf", &x1, &y1, &x, &y);
    		while (m--) {
    			scanf("%lf%lf", &xn, &yn);
    			s += (cs = g(x1, y1, x, y, xn, yn));
    			gsx += (x1 + x + xn) * cs / 3;
    			gsy += (y1 + y + yn) * cs / 3;
    			x = xn;
    			y = yn;
    		}
    		printf("%.3f %.3f\n", fabsf(s),
    				(s == 0 ? 0.0 : fabsf((gsx + gsy) / s)));
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，208人围观）

还没有评论，来说两句吧...

相关阅读

相关 NYOJ3—多边形重心问题（计算几何）&&hdu1115 Lifting the Stone

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

深藏阁楼爱情的钟/ 2024年02月17日 19:20/ 0 赞/ 42 阅读

相关树的重心专题

解题思路：选择一个节点作为根，设dp\[i\]表示以i为根的树的总节点个数，dp\[i\]=满足j为其子节点的的d\[j\]之和再加1（根节点）。只需在dfs过程中找到最大的子

清疚/ 2023年08月17日 16:26/ 0 赞/ 123 阅读

相关杂文 -- 面试重心

杂文 – 面试重心又到年底了，写一篇文章也是理所应当，现在外面的技术都比较新，新项目都在用新技术，而一些老项目都在维护老项目，沉逾的框架虽然没有现在的技术新但是比较老。

桃扇骨/ 2023年06月12日 13:28/ 0 赞/ 10 阅读

相关树的重心

题目描述给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一

浅浅的花香味﹌/ 2022年10月25日 15:27/ 0 赞/ 167 阅读

相关用计算机求解重心法,excel求解精确重心法

精确重心法问题描述假设有一系列点代表生产地和需求地，各自有一定量货物需要以一定的运输费率运向待定的仓库，或从仓库运出，现在要确定仓库应该位于何处才能使总运输成本最小？这是

╰半橙微兮°/ 2022年10月07日 04:47/ 0 赞/ 170 阅读

相关多边形重心问题

描述在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接，（第一个和最后一个连接），所有线段不和其他线段相交，但是可以重合，可得到一个多边形或一条

Dear 丶/ 2022年08月11日 16:54/ 0 赞/ 209 阅读

相关求重心的板子

define _CRT_SECURE_NO_WARNINGS include <cstdio> include <cstdlib>

快来打我*/ 2022年06月05日 23:46/ 0 赞/ 143 阅读

相关多边形

import turtle as t t.setup(650,350,200,200) t.penup() t.fd(50) t.pen

亦凉/ 2022年03月27日 13:26/ 0 赞/ 562 阅读

相关 python 不规则多边形计算重心点

因为要在经纬度地图上求一个不规则多边形的重心重心相对中心的区别对于不规则多边形来说是有很大差异的 def get_centerpoint(lis):

向右看齐/ 2022年02月20日 00:18/ 0 赞/ 569 阅读

相关 HDU 6567 Cotree 树的重心（树的重心）

题意：给定n的点，n-2条边，也就是给出了两棵树，要求加一条边连接两棵树并使得连接好的这棵树上任意两点距离和最小。分析：树的重心一个很重要的性质就是所有点到当前点的距

川长思鸟来/ 2021年10月18日 07:48/ 0 赞/ 264 阅读