---
tags: code
---

# Convex Hull (凸包)
[TOC]
## Definition
給定 $N$ 個點，包圍這 $N$ 個點且面積最小的凸多邊形即稱為凸包。
## Algorithms
### Andrew’s Monotone Chain
#### Method
上凸包 $+$ 下凸包 $=$ 完整的凸包。
先將點依照 $(x,y)$ 座標排序，
(下凸包)由左到右檢查該點是否合法並新增/刪除該點，
(上凸包)由右到左重覆如上動作。

觀察凸包，
若從左到右依序看點，
會發現下一個向量都是在前一個向量的逆時鐘方向，
因此合不合法的判斷就是，
如果 $\overrightarrow{P_{i} P_{i+1}} \times \overrightarrow{P_{i} P_{i+2}} \le 0$ 代表前一個點會在凸包裡面，
而不會在凸包上，
就可以把前一個點刪掉，
重覆這個動作直到合法，
再把新的點加進去凸包裡面。

#### Features
- 方便撰寫
- 可解決凸包有重疊的點、共線的點、退化成線段和點的情況
- 獲得的凸包是逆時針排序好的，方便處理行列式等問題
- 複雜度 $O(N\log N)$

### Code

struct point {
	int x, y;
	bool operator<(const point& rhs) const {return x == rhs.x ? y < rhs.y : x < rhs.x;}
	point operator-(const point& rhs) const {return {x - rhs.x, y - rhs.y};}
	friend int cross(const point& o, const point& a, const point& b) {
		point lhs = a - o, rhs = b - o;
		return lhs.x * rhs.y - rhs.x * lhs.y;
	}
	friend istream& operator>>(istream& is, point& p) {return is >> p.x >> p.y;}
	point(int _x = 0, int _y = 0): x(_x), y(_y) {}
};

vector<point> convex_hull(vector<point>& hull) {
	if (hull.size() <= 2) return hull;
	sort(hull.begin(), hull.end());
	vector<point> stk;
	int n = (int)hull.size();
	for (int i = 0; i < n; i++) {
		while ((int)stk.size() >= 2 && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	for (int i = n - 2, t = (int)stk.size() + 1; i >= 0; i--) {
		while ((int)stk.size() >= t && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	return stk.pop_back(), stk;
}

## Problems
:::spoiler `TIOJ 1178. Convex Hull`

#define ALL(x) (x).begin(), (x).end()
using ll = long long;

struct point {
	ll x, y;
	bool operator<(const point& rhs) const {return x == rhs.x ? y < rhs.y : x < rhs.x;}
	point operator-(const point& rhs) const {return {x - rhs.x, y - rhs.y};}
	friend ll cross(const point& o, const point& a, const point& b) {
		point lhs = a - o, rhs = b - o;
		return lhs.x * rhs.y - rhs.x * lhs.y;
	}
	friend istream& operator>>(istream& is, point& p) {return is >> p.x >> p.y;}
	point(ll _x = 0, ll _y = 0): x(_x), y(_y) {}
};

vector<point> convex_hull(vector<point>& hull) {
	if (hull.size() <= 2) return hull;
	sort(ALL(hull));
	vector<point> stk;
	int n = (int)hull.size();
	for (int i = 0; i < n; i++) {
		while ((int)stk.size() >= 2 && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	for (int i = n - 2, t = (int)stk.size() + 1; i >= 0; i--) {
		while ((int)stk.size() >= t && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	return stk.pop_back(), stk;
}

void solve() {
	int n; cin >> n;
	vector<point> v(n);
	for (auto& i : v) cin >> i;
	cout << convex_hull(v).size() << '\n';
}

:::

:::spoiler `TIOJ 1280. 領土 (Territory)`

#define ALL(x) (x).begin(), (x).end()
using ll = long long;
struct point {
	ll x, y;
	bool operator<(const point& rhs) const {return x == rhs.x ? y < rhs.y : x < rhs.x;}
	point operator-(const point& rhs) const {return {x - rhs.x, y - rhs.y};}
	friend ll cross(const point& o, const point& a, const point& b) {
		point lhs = a - o, rhs = b - o;
		return lhs.x * rhs.y - rhs.x * lhs.y;
	}
	friend istream& operator>>(istream& is, point& p) {return is >> p.x >> p.y;}
	point(ll _x = 0, ll _y = 0): x(_x), y(_y) {}
};

vector<point> convex_hull(vector<point>& hull) {
	if (hull.size() <= 2) return hull;
	sort(ALL(hull));
	vector<point> stk;
	int n = (int)hull.size();
	for (int i = 0; i < n; i++) {
		while ((int)stk.size() >= 2 && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	for (int i = n - 2, t = (int)stk.size() + 1; i >= 0; i--) {
		while ((int)stk.size() >= t && cross(stk.end()[-2], stk.end()[-1], hull[i]) <= 0) stk.pop_back();
		stk.push_back(hull[i]);
	}
	return stk;
}

:::