题意:无序地给出一个凸包的所有点,求凸包的质心。
因为凸包是无序的,所以还要先处理一番。
Graham_scan凸包算法:
对点进行简单排序后,再进行极角排序。可以得到凸包上的部分点,但凸包的形状是完整的(即某些共线点可能丢弃)。
复杂度O(hn)(n为总点数,h为凸包上的点数,不考虑排序...)
Andrew凸包算法:
对点进行排序后(非极角排序),正向循环找出上凸包,再逆向循环找出下凸包。
优点:可以找出凸包上所有的点。
实际比较之后发现Andrew比Graham_scan要快。
求质心:
三角形的质心在(A+B+C)/3的位置。可以通过把多边形进行三角剖分,把每个三角形的质心求出来,再对这些质心求面积加权后的平均值。
(可令原点为所有三角形的C点)。
#include <algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; #define MAXN 110 #define eps 1e-10 #define max(x, y) (x > y ? x : y) #define min(x, y) (x < y ? x : y) #define sig(x) ((x > eps) - (x < -eps)) #define cross(o, a, b) ((p[a] - p[o]) ^ (p[b] - p[o])) const double pi = acos(-1.0); typedef struct Point { double x, y; Point() {} Point(double _x, double _y): x(_x), y(_y) {} bool operator <(const Point &argu) const { return sig(x - argu.x) == 0 ? y < argu.y : x < argu.x; } double dis(const Point &argu) const { return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y)); } double dis2(const Point &argu) const { return (x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y); } double operator ^(const Point &argu) const { return x * argu.y - y * argu.x; } double operator *(const Point &argu) const { return x * argu.x + y * argu.y; } Point operator -(const Point &argu) const { return Point(x - argu.x, y - argu.y); } double len2() const { return x * x + y * y; } double len() const { return sqrt(x * x + y * y); } void in() { scanf("%lf%lf", &x, &y); } void out() { printf("%.3lf %.3lf\n", x, y); } }Vector; void BaryCenter(Point p[], int q[], int n, Point &c) { c.x = c.y = 0; double area = 0; for(int i = 1; i <= n; i++) { double area2 = (p[q[i - 1]] ^ p[q[i % n]]); c.x += (p[q[i - 1]].x + p[q[i % n]].x) / 3 * area2; c.y += (p[q[i - 1]].y + p[q[i % n]].y) / 3 * area2; area += area2; } c.x /= area; c.y /= area; } inline double Cross(Point p[], int o, int a, int b) { return (p[a] - p[o]) ^ (p[b] - p[o]); } //Point minp; //bool cmp(Point a, Point b) //{ // double anga = atan2(a.y - minp.y, a.x - minp.x); // double angb = atan2(b.y - minp.y, b.x - minp.x); // return anga < angb; //} int ConvexHull(Point p[], int n, int q[]) { sort(p, p + n); // minp = p[0]; // sort(p + 1, p + n, cmp); int top = 0; for(int i = 0; i < n; i++) { while(top > 1 && Cross(p, q[top - 2], q[top - 1], i) < 0) top--; q[top++] = i; } int tmp = top; for(int i = n - 2; i >= 0; i--) { while(top > tmp && Cross(p, q[top - 2], q[top - 1], i) < 0) top--; q[top++] = i; } top--; return top; } Point pp[MAXN], c; int n, q[MAXN]; void solve() { ConvexHull(pp, n, q); BaryCenter(pp, q, n, c); c.out(); } int main() { // freopen("A.in", "r", stdin); while(scanf("%d", &n) && (n > 2)) { for(int i = 0; i < n; i++) pp[i].in(); solve(); } return 0; }