山姆的競程日記

從綠牌開始的旅途

0%

凸包 Convex Hull

發表於 Disqus：

今天也是不知道該學什麼

剛好想到這也是一個我還沒有學過的東西

因此 今天就決定來紀錄一下凸包與動態凸包

什麼是凸包?

先附上維基百科的定義

看起來很數學 不過他的定義簡單來說就是一個平面上有很多個點

能夠包住所有點且面積最小的凸多邊形就叫作凸包

如何找到凸包？

要求一個平面上的凸包 比較常見的有兩種作法

一、Andrew’s Monotone Chain

這個是利用單調隊列的方式來得到凸包

我們先依照點的x座標做排序，再以y座標做排序

分別求出下凸包以及上凸包

用stack去維護每個點

當向量的外積小於等於零時 就pop

複雜度: $O(nlogn)$

二、Graham’s Scan

先找到最左下的點($y 座標最小的最左邊的點）

並用其他點對這個點做極角排序

同樣用一個stack來維護凸包上的點

複雜度： $O(nlogn)$

三、實作凸包演算法

我們用Andrew’s Monotone Chain來找凸包

至於Graham’s Scan 大家可以自己去找相關資料

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

template<typename T>
pair<T,T> operator - (pair<T,T> a, pair<T,T> b){
	return make_pair(a.first-b.first,a.second-b.second);
}

template<typename T>
T cross(pair<T,T> a, pair<T,T> b){
	return a.first*b.second-a.second*b.first;
}

template<typename T>
vector<pair<T,T>> getCH(vector<pair<T,T>> v){
	int n = v.size();
	sort(v.begin(),v.end());
	vector<pair<T,T>> hull;
	for(int i = 0;i < 2;i++){
		int t = hull.size();
		for(auto x : v){
			while(hull.size()-t>=2&&cross(hull[hull.size()-1]-hull[hull.size()-2],x-hull[hull.size()-2])<=0)
				hull.pop_back();
			hull.push_back(x);
		}
		hull.pop_back();
		reverse(v.begin(), v.end());
	}
	return hull;
}

凸包 例題

一、TIOJ 1178 - Convex Hull

題目連結

這題就是凸包的裸題 求出凸包之後 輸出有幾個頂點就好

二、Zerojudge a871 - Museum Area

題目連結

這題就是求凸包面積 要找凸包的面積就用外積和/2 （要記得逆時針）

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//這裡省略求凸包的程式碼
signed main(){
	fastio
	int n;
	while(cin >> n){
		vector<pair<double,double>> v;
		for(int i = 0;i < n;i++){
			double x,y;
			cin >> x >> y;
			v.emplace_back(x,y);
		}
		vector<pair<double,double>> CH = getCH(v);
		double ans = 0;
		for(double i = 2;i < n;i++){
			ans += cross(CH[i-1]-CH[0],CH[i]-CH[0]);
		}
		cout << fixed << setprecision(2) << ans/2.0 << "\n";
	}
}

三、Zerojudge d546 - 減多邊形

題目連結

這題是98年的北市賽題目

因為一開始給的點就是逆時針的 我們用凸包面積減去原多邊形面積再除以 $a$ 的 $ceil$ 就是答案了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main(){
	fastio
	int n,a;
	cin >> n >> a;
	vector<pair<double,double>> v;
	for(int i = 0;i < n;i++){
		double x,y;
		cin >> x >> y;
		v.emplace_back(x,y);
	}
	double tmp = 0; //原多邊形面積
	for(int i = 2;i < n;i++){
		tmp += cross(v[i-1]-v[0],v[i]-v[0]);
	}
	tmp/=2;
	double tmp2 = 0; //凸包面積
	v = getCH(v);
	for(int i = 2;i < n;i++){
		tmp2 += cross(v[i-1]-v[0],v[i]-v[0]);
	}
	tmp2/=2;
	cout << (int)ceil((tmp2-tmp)/a) << "\n";
}

四、TIOJ 1280 - 領土 (Territory)

題目連結

這題是103年的北市賽題目

也是直接求凸包面積

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long 
using namespace std;

pair<int,int> operator - (pair<int,int> a, pair<int,int> b){
	return {a.first-b.first,a.second-b.second};
}

int cross(pair<int,int> a, pair<int,int> b){
	return a.first*b.second-a.second*b.first;
}

vector<pair<int,int>> getCH(vector<pair<int,int>> v){
	int n = v.size();
	sort(v.begin(),v.end());
	vector<pair<int,int>> ans;
	for(int i = 0;i < 2;i++){
		int t = ans.size();
		for(auto x : v){
			while(ans.size()-t >= 2 && cross(ans.back()-ans[ans.size()-2],x-ans[ans.size()-2])<=0){
				ans.pop_back();
			}
			ans.push_back(x);
		}
		ans.pop_back();
		reverse(v.begin(),v.end());
	}
	return ans;
}

signed main(){
	fastio
	int n;
	cin >> n;
	vector<pair<int,int>> v;
	for(int i = 0;i < n;i++){
		int x,y;
		cin >> x >> y;
		v.emplace_back(x,y);
	}
	int ans = 0;
	v = getCH(v);
	for(int i = 2;i < v.size();i++){
		ans += cross(v[i-1]-v[0],v[i]-v[0]);
	}
	cout << (ans+1)/2 << "\n";
}

動態凸包

我們可以用一個例題來理解動態凸包是什麼
Codeforces 70D

有 $q$ 個操作與詢問

每次操作在平面上加入一個點 $(x,y)$

每次詢問一個點 $(x,y)$ 是否在凸包內

這題想了一下之後 你可能會覺得我們要怎麼去維護新的凸包呢？

假如我們用的是Andrew’s Monotone Chain

我們所有點都是依 $x,y$ 座標進行排序的

或者我們用的是極角排序的 Graham’s Scan

有一種資料結構能夠幫助我們做到這一點

那就是 std::set !

後續代補