凸包真是一个神奇的算法。。
概念
- 凸包，我理解为凸多边形
- 叉积 对于向量AB和向量BC，记向量AB*向量BC = AB * BC * sin ∠ABC，而叉积的绝对值其实就是S△ABC/2
对于平面上的一些点，我们要求凸包上所有的点，可以使用Graham算法 时间复杂度O（nlogn）
思路
先找到最左下的点，把其他的点按叉积排序。然后维护一个堆栈，每次利用叉积和栈顶比较判断当前枚举到的点是否是凸包上的点，是则弹出栈顶元素
具体算法-
周长
直接所有相邻两点距离相加 -
面积
多边形面积直接利用公式，用叉积计算
常熟巨大的丑陋代码
# include# include # include # include # include # include # define RG register# define IL inline# define ll long long# define mem(a, b) memset(a, b, sizeof(a))# define Min(a, b) (((a) > (b)) ? (b) : (a))# define Max(a, b) (((a) < (b)) ? (b) : (a))# define Sqr(a) ((a) * (a))using namespace std;const int MAXN = 50001;int n, top;struct Point{ double x, y, len;} p[MAXN], Point_A, s[MAXN]; //最左下的点 //求叉积(向量ab，向量ac) IL double Cross(Point a, Point b, Point c){ return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);}IL double Dis(Point a, Point b){ return sqrt(Sqr(a.x - b.x) + Sqr(a.y - b.y));}//极角排序 IL bool Cmp(Point a, Point b){ RG double x = Cross(Point_A, a, b); if(x > 0) return 1; else if(x < 0) return 0; a.len = Dis(Point_A, a); b.len = Dis(Point_A, b); return a.len < b.len;}//查找起始点，最左下IL void Find(){ RG int temp = 0; RG Point a = p[1]; for(RG int i = 2; i <= n; i++) if(p[i].y < a.y || p[i].y == a.y && p[i].x < a.x){ a = p[i]; temp = i; } p[temp] = p[1]; p[1] = a; Point_A = a;//保存起始点}//求凸包周长IL double Length(){ RG double sum = 0; for(RG int i = 1; i <= top; i++) sum += Dis(s[i - 1], s[i]); return sum;}//计算面积IL double Area(){ RG double sum = 0; for(RG int i = 1; i < top - 1; i++) sum += Cross(s[0], s[i], s[i + 1]); sum = fabs(sum) / 2; return sum;}IL void Graham(){ Find(); sort(p + 2, p + n + 1, Cmp); s[0] = p[1]; s[1] = p[2]; for(RG int i = 3; i <= n; i++){ while(Cross(s[top - 1], s[top], p[i]) <= 0 && top) top--; s[++top] = p[i]; } s[++top] = p[1];}int main(){ while(~scanf("%d", &n) && n){ top = 1; for(RG int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); Graham(); cout << top << " " << length() << " " << Area() << endl; } return 0;}
板子题 1.Surround the Trees HDU - 1392 2.Cows POJ - 3348