凸包模板 / Andrew算法 poj3348

前言

凸包是计算几何中相对基础的内容，主流解法为Graham扫描法

Andrew算法是它的一个变种，应用也十分广泛，但两者也有区别

Graham类算法更偏向于利用角的关系，因此可能会产生较大的常数

而Andrew算法则更偏向于利用横纵坐标的关系，两者的时间复杂度均为 O ( n log ⁡ n ) O(n \log n) O(nlogn)

一、例题 poj3348

题目链接 poj-3348

二、思路及代码 1.思路

很单纯的一道凸包题，再配合上叉积求面积，直接套模板

2.代码

代码如下：

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 11000;
struct point {
  int x, y;
  point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  point operator-(const point a) const { return point(x - a.x, y - a.y); }
} p[maxn], hull[maxn];  // 原点集  凸包序列
bool cmp(point a, point b) {
  if (a.x == b.x) return a.y = 0; i--) {  //下部
    while (cnt > upcnt) {
      tmp = cross(hull[cnt - 1] - hull[cnt - 2], p[i] - hull[cnt - 2]);
      if (tmp > 0) break;
      cnt--;
    }
    hull[cnt++] = p[i];
  }
  if (n > 1) cnt--;
  return cnt;  // 凸包中元素个数
}
double area(point hull[], int cnt) {
  double ans = 0;
  for (int i = 0; i