文档章节

nyoj 3 多边形重心问题

o
 osc_x4h57ch8
发布于 2018/04/24 01:32
字数 581
阅读 0
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

多边形重心问题

时间限制: 3000 ms  |  内存限制:65535 KB
难度: 5
 
描述
  在某个多边形上,取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

/**
    注意:
        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;
} 

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

我在广州面试的那些事

背景   这次的疫情让原本看似有序的但是浮躁的社会彻底打乱了,不少劳动者在多年稳定的节奏也随之而变,而我在于其中放慢了步调,从5月份放弃了一份工作同时拒绝了两份offer后回家休息加造...

osc_d8t0zzig
27分钟前
5
0
快速读入、输出,及其他模板

头 如果你在我博客里,读到某个代码没有头。请把这段复制到代码前面: //problem:#include <bits/stdc++.h>using namespace std;#define pb push_back#define mk make_pair#define lo...

osc_k12h8kbw
28分钟前
5
0
彻底解决unable to find valid certification path to requested target

安装证书。 下载证书 第一步是要下载证书 去你程序要访问的网站,点击那个锁按钮,并点击查看详情(chrome浏览器) 点击View certificate 点击详细信息 复制到文件 下一步 选择格式 生成的名...

osc_r9yyhhqz
30分钟前
10
0
reg007最新邀请码!!!

需要的小伙伴留邮箱我邀请你们。

osc_50znnx42
32分钟前
9
0
Python正课目录

本文内容皆为作者原创,如需转载,请注明出处:https://www.cnblogs.com/xuexianqi/p/12515420.html My: 我的整理 我的字典 luffy上线 First:安装教程 PyCharm2020.1破解教程 Python安装1...

osc_wxsc35it
34分钟前
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部