[HDU1115] Lifting the Stone

2017年8月26日

求多边形的重心。

这个就讲得很好:http://www.cnblogs.com/jbelial/archive/2011/08/08/2131165.html

简单讲,三角形的重心就是三个坐标的算术平均数,一堆有质量的点就是就是坐标加质量为权的平均数。而对于这个多边形内凹的话,凹下去就变成负的了。把多边形分成多个三角形,然后这些三角形都当成一堆有质量的点就可以了。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1115

#include <bits/stdc++.h>
using namespace std;
struct Point {
  double x, y;
  Point operator - (const Point &op) const {
    return (Point){x - op.x, y - op.y};
  }
};
double cross(Point a, Point b)
{
  return a.x * b.y - a.y * b.x;
}
int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    double sum = 0;
    double sum_x = 0, sum_y = 0;
    Point a, b, c;
    scanf("%lf %lf", &a.x, &a.y);
    scanf("%lf %lf", &b.x, &b.y);
    for (int i = 2; i < n; i++) {
      scanf("%lf %lf", &c.x, &c.y);
      double s = cross(b - a, c - a) / 2;
      sum += s;
      sum_x += (a.x + b.x + c.x) * s;
      sum_y += (a.y + b.y + c.y) * s;
      b = c;
    }
    printf("%.2lf %.2lf\n", sum_x / sum / 3.0, sum_y / sum / 3.0);
  }
  return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注