NYOJ 3(多边形重心)-阿里云开发者社区

NYOJ 3(多边形重心)

2012-08-03 666

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 多边形重心问题时间限制：3000 ms | 内存限制：65535 KB 难度：5 描述在某个多边形上，取n个点，这n个点顺序给出，按照给出顺序将相邻的点用直线连接，（第一个和最后一个连接），所有线段不和其他线段相交，但是可以重合，可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形；如果是一条线段,我们定义面积为0，重心坐标为（0,0）.

多边形重心问题

时间限制： 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

//http://www.cnblogs.com/jbelial/archive/2011/08/08/2131165.html
//实际上没必要用结构体 
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 10000;
const double cmp = 1e-8;
typedef struct Node
{
    double x,y;
}Node;
double area(double x1,double y1,double x2,double y2,double x3,double y3)//有向面积 
{//判断三点是否共线：有向面积为0 
    return 1.0/2*((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
} 
Node ch[N];
int main()
{
    int i, j, T;
    scanf( "%d" , &T);
    while(T--)
    {
        int num;//既然是多边形，则num至少为3 
        memset(ch,0,sizeof(ch));
        scanf("%d", &num);
        scanf( "%lf %lf",&ch[1].x, &ch[1].y);
        scanf( "%lf %lf",&ch[2].x, &ch[2].y);
        int i;
        double sum_x=ch[1].x,sum_y=ch[1].y,sum_area=0;
        double gx,gy;//每个三角形重心坐标 
        double  sum_1x=0, sum_1y=0;  
        for(i=3;i<=num;i++)
        { 
            sum_x=ch[1].x,sum_y=ch[1].y;//必须在for内初始化 
            scanf( "%lf %lf",&ch[i].x, &ch[i].y);
            sum_x+=ch[i].x + ch[i-1].x;
            sum_y+=ch[i].y + ch[i-1].y;
            gx=sum_x/3.0;
            gy=sum_y/3.0;
            sum_area+=area(ch[1].x,ch[1].y,ch[i].x,ch[i].y,ch[i-1].x,ch[i-1].y);
            sum_1x+=gx*area(ch[1].x,ch[1].y,ch[i].x,ch[i].y,ch[i-1].x,ch[i-1].y);//横坐标分子 
            //sum_2x+=area(ch[1].x,ch[1].y,ch[i].x,ch[i].y,ch[i-1].x,ch[i-1].y);//横坐标分母 
            sum_1y+=gy*area(ch[1].x,ch[1].y,ch[i].x,ch[i].y,ch[i-1].x,ch[i-1].y);//纵坐标分子 
            //sum_2y+=area(ch[1].x,ch[1].y,ch[i].x,ch[i].y,ch[i-1].x,ch[i-1].y);//纵坐标分母
        }
        double sum=0;
        if(sum_area!=0) 
            sum=sum_1x/sum_area+sum_1y/sum_area; 
        if(fabs(sum_area-cmp)==0)
            printf( "0.000 0.000\n");
        else
            printf("%.3lf %.3lf\n",sum_area, sum);
    }
    return 0;
}

NYOJ 3(多边形重心)

多边形重心问题

热门文章

最新文章

相关电子书