HDU 1115 求多边形重心

简介:

一个均匀的多边形重心为 横纵坐标和分别除以六倍的面积。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
using namespace std;
struct point
{
    double x,y;
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    void print()
    {
        printf("%.2f %.2f\n",x,y);
    }
};
double cross(point i,point j,point k)
{
    return (j.x-i.x)*(k.y-i.y)-(k.x-i.x)*(j.y-i.y);
}
point Gravity(point p[],int n)
{
    point O,t;
    O.x = O.y = 0;
    t.x = t.y = 0;
    p[n] = p[0];
    double A = 0;
    for(int i=0; i<n; i++)
        A += cross(O,p[i],p[i+1]);
    A /= 2.0;
    for(int i=0; i<n; i++)
    {
        t.x += (p[i].x + p[i+1].x) * cross(O,p[i],p[i+1]);
        t.y += (p[i].y + p[i+1].y) * cross(O,p[i],p[i+1]);
    }
    t.x /= 6*A;
    t.y /= 6*A;
    return t;
}
point data[1000005];
int main()
{
    int t;
    int n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)data[i].input();
        point t=Gravity(data,n);
        t.print();
    }
    return 0;
}


目录
相关文章
|
6月前
poj-1611-The Suspects
poj-1611-The Suspects
28 0
|
机器人 Python
凸包(Convex Hull)
凸包(Convex Hull)是一个计算几何中的概念,它表示在平面上或空间中一组点集的最小凸包。简单来说,就是一个凸多边形,这个多边形的所有顶点都是点集中最外部的点,且所有内部角都小于 180 度。凸包的计算可以用于许多场景,如碰撞检测、数据压缩和最近邻搜索等。
193 6
|
机器学习/深度学习
Leecode 892. 三维形体的表面积
Leecode 892. 三维形体的表面积
61 0
2021杭电多校第八场 HDU7063-Square Card(求两圆相交面积)
2021杭电多校第八场 HDU7063-Square Card(求两圆相交面积)
74 0
2021杭电多校第八场 HDU7063-Square Card(求两圆相交面积)
|
人工智能 算法
832 翻转图像 leetcode
832 翻转图像 leetcode
101 0
POJ-2251,Dungeon Master(三维迷宫BFS)
POJ-2251,Dungeon Master(三维迷宫BFS)
POJ - 1032: Parliament
POJ - 1032: Parliament
104 0
POJ 1012 Joseph
Joseph Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 53862   Accepted: 20551 Description The Joseph's problem is notoriously known.
841 0