多边形重心问题

Dear 丶 2022-08-11 16:54 192阅读 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 条评论，192人围观）

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

相关阅读

相关树的重心

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

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

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

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

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

相关多边形重心问题

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

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

相关 pointPolygonTest多边形检测

根据官网提供的程序 include "opencv2/highgui/highgui.hpp" include "opencv2/imgproc/imgpro

逃离我推掉我的手/ 2022年06月15日 20:06/ 0 赞/ 507 阅读

相关树的重心 Shaass the Great

题目:[CodeForces - 294E][] 题意: 有一棵树，切断某条边之后，重造一条长度一样的边连接两个新子树，使得新子树所有点到所有点的距离和最小。

偏执的太偏执、/ 2022年06月14日 06:24/ 0 赞/ 181 阅读

相关求重心的板子

define _CRT_SECURE_NO_WARNINGS include <cstdio> include <cstdlib>

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

相关多边形

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

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

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

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

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

相关多边形游戏

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 多边形游戏是一个单人玩的游戏，开始时有一个由n个顶

秒速五厘米/ 2022年01月15日 01:51/ 0 赞/ 286 阅读

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

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

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