convex hull

凸包:給數個點,求能包住所有點的最小點數量

Andrew’s Monotone Chain演算法

1. 把所有點排序(x由小到大,同y由小到大)
2. 依逆時針尋找下凸包
3. 依逆時針尋找上凸包

排序

//v[]測資
struct point{
    int x,y;
};

bool cmp(point a,point b){
    if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}

//----main----
sort(v.begin(),v.end(),cmp);

尋找下凸包

由於排好序的關係,依序為最左下角的點到最右上角的點,只要依序掃一遍陣列,並判斷是否為最外圈的點,就能蒐集到下凸包

外積

如何判斷是否為最外圈的點,就要用到外積,高二下學的外積是用於空間座標(x,y,z),但我們的凸包是平面座標,所以只要把z帶0即可

因為下凸包是逆時針旋轉,所以只要判斷3個點(O,A,B)組成的2個向量(OA,OB)外積即可

如果向量外積<0: 依據右手定則,由OA轉到OB拇指向下(如下圖),外積為負,此時就可省略A點,把A點移除,依序重複此步驟直到向量外積為正

如果向量外積=0: 此時3點共線(圖下圖),可省略A直接連到B

如果向量外積>0 :此時為逆時針旋轉,符合下包凸條件,加入包凸

Code:

double cross(point o,point a,point b){
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}

//---main----
point stack[MAXN];
int top=0;

for(int i=0;i<n;i++){
    while(top-2>=0 && cross(stack[top-2],stack[top-1],v[i]<=0){
        top--;
    }
    stack[top++]=v[i];
}

尋找上凸包

同理下凸包,唯一要注意的是:因為凸包是圍一圈的,所以下凸包的終點=上凸包的起點,上凸包的終點=下凸包的起點,所以要扣掉這兩個重複的點

top--;  //扣掉下凸包的終點
for(int i=n-1,lowest=top;i>=0;i--){
    while(top-2>=lowest && cross(stack[top-2],stack[top-1],v[i])<=0){
        top--;
    }
    stack[top++]=v[i];
}
top--;  //扣掉上凸包的終點

Code

point stack[MAXN];
int top=0;
for(int i=0;i<n;i++){
    while(top-2>=0 && cross(stack[top-2],stack[top-1],v[i])<=0){
        top--;
    }
    stack[top++]=v[i];
}
top--;
for(int i=n-1,lowest=top;i>=0;i--){
    while(top-2>=lowest && cross(stack[top-2],stack[top-1],v[i])<=0){
        top--;
    }
    stack[top++]=v[i];
}
top--;

TOIJ 1178 . Convex Hull

#include <bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;

struct point{
  int x,y;
};

vector<point> v;
int n,ans;

bool cmp(point a,point b){
  if(a.x==b.x) return a.y<b.y;
  else return a.x<b.x;
}

double cross(point o,point a,point b){
  return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}

void Andrew_monotone_chain(){
  sort(v.begin(),v.end(),cmp);
  point stack[MAXN];
  int top=0;
    for(int i=0;i<n;i++){
      while(top-2>=0 && cross(stack[top-2],stack[top-1],v[i])<=0){
        top--;
      }
      stack[top++]=v[i];
    }
    top--;
    for(int i=n-1,lowest=top;i>=0;i--){
      while(top-2>=lowest && cross(stack[top-2],stack[top-1],v[i])<=0){
        top--;
      }
      stack[top++]=v[i];
    }
    top--;
    ans=top;
}

signed main(){
  int x,y;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> x >> y;
    v.push_back({x,y});
  }
  Andrew_monotone_chain();
  cout << ans << '\n';
  return 0;
}