求凸包面積（分治法）
求凸包面積的方式有很多，本次我所講的是利用分支法來求解該題，其它就不在講述~~(狗頭)~~,大部分都了解分治法是將大問題化成小問題求解，恰恰好這種求凸包面積很適合用分支法，個人覺得這樣代碼較短
下面結合著例題講解：
麥兜是個淘氣的孩子，一天，他在玩鋼筆的時候把墨水灑在了白色的墻上，再過一會，麥兜媽就要回來了，麥兜為了不讓媽媽知道這件事情，就想用一個白色的凸多邊形把墻上的墨點蓋住，你能告訴麥兜最小需要面積多大的凸多邊形才能把這些墨點蓋住嗎？ 現在，給出了這些墨點的坐標，請幫助麥兜計算出覆寫這些墨點的最小凸多邊形的面積，
輸入:
多組測驗資料，第一行是一個整數T，表明一共有T組測驗資料，
每組測驗資料的第一行是一個正整數N(0< N < = 105)，表明了墨點的數量，接下來的N行每行包含了兩個整數Xi和Yi（0<=Xi,Yi<=2000），表示每個墨點的坐標，每行的坐標間可能包含多個空格，
輸出:
每行輸出一組測驗資料的結果，只需輸出最小凸多邊形的面積，面積是個實數，小數點后面保留一位即可，不需要多余的空格，
樣例輸入
2
4
0 0
1 0
0 1
1 1
2
0 0
0 1
樣例輸出
1.0
0.0
先上代碼吧，可能我的代碼比我的講解更清楚(自嘲)
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
const int maxn = 1001;
// 記錄結果
double area = 0.0;
struct node{
int x;
int y;
}a[maxn];
bool cmp(node a, node b) {
if(a.x != b.x) {
return a.x < b.x;
}
return a.y < b.y;
}
// 根據叉乘判斷方向
// 判斷ac向量在ab向量的順時針方向還是逆時針方向
// 回傳 true表示逆時針方向
// 回傳 false表示順時針方向
bool direction(node a, node b, node c) {
// ab向量的坐標
int x1 = b.x - a.x;
int y1 = b.y - a.x;
// ac向量的坐標
int x2 = c.x - a.x;
int y2 = c.y - a.y;
if(x1 * y2 - y1 * x2 > 0)
return true;
return false;
}
/*
求任意三個點連線圍成的三角形的面積
*/
double getArea(node a, node b, node c) {
// 根據行列式的性質可知，三角形的面積等于三階行列式的一半
return fabs(0.5 * (a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y));
}
/*
計算上下凸包的面積，當flag=true,求凸包上半部分的面積
當flag=false，求凸包下半部分的面積
left, right 分別表示凸包區間的左右端點的橫坐標，利用分治法進一步求其
整個凸包的面積
*/
void caculate(bool flag, int left, int right) {
/*
回圈遍歷的left，right之間的每個點，在left和right指定的一側時
并且求其最大面積
*/
double temp = -1.0;
int k = 0; // 記錄面積最大的那個點的橫坐標
for(int i = left + 1; i <= right - 1; i++)
{
// 判斷當上下凸包時，該點是否在left和right連線指定的一側，如果沒在就不考慮該點
if(direction(a[left], a[right], a[i]) != flag) {
continue;
}
if(temp < getArea(a[left], a[right], a[i])) {
temp = getArea(a[left], a[right], a[i]);
k = i;
}
}
// 當k沒有改變證明此時只有兩個點不構成三角形，故結束遞回
if(k == 0)
return;
area += temp;
caculate(flag, left, k);
caculate(flag, k, right);
}
int main() {
int t;
cin >> t;
while(t--) {
area = 0.0;
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i].x >> a[i].y;
}
sort(a + 1, a + n + 1, cmp);
// 求上凸包的面積
caculate(true, 1, n);
// 求下凸包的面積
caculate(false,1, n);
cout << fixed << setprecision(1);
cout << area << endl;
}
return 0;
}
相信看了以上的代碼大概的有一些自己的思路了吧，就我而言，我所理解的凸包就把一個一個的點看成一個一個的釘子，這時用一個皮筋給它包住，此時這個皮筋就是凸包的邊界，對于求這個題我們最重要的就是找到那些點是屬于凸包的點，剛開始將各個頂點排序，我們可以想到橫坐標最小和最大的點一定是凸包的頂點，
找到左右兩個端點后我們將其分為上下兩部分分開算，上下兩個部分分別進行遞回，求出其各個面積，首先考慮上部分，對于上部分，要確定那個點是凸包的點我們立即就可以想到離AB直線最遠的點一定是凸包的頂點，換而言之就是在上半部分找到一個點使得該點與AB兩點組成的三角形面積最大，計算出該面積
假設C點是距離AB最遠的點，計算出三角形ABC的面積，這是三角形ABC里面的點的面積就不用管了，是不是對于直線AB上部分我們是不是求出了一些面積了（三角形ABC的面積），剩下的就是直線AC的外側的和BC外側的點的面積沒有求了，其實你你理解了上面的做法，接下來就很容易啦，用同樣的方法求直線AC和BC外的凸包的點，好啦，本次求凸包的面積就講完了，是不是感覺結束的很突兀，如還有疑問的話可以私信博主本人額
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/216105.html
標籤：其他