Research cause: the elder martial brother needs to integrate the convex hull algorithm and start learning the calculation and solution of convex hull and related applications with a curious attitude.

Cross product

It's important to understand the cross product first.

Cross product application:
Find the area of any N-sided shape:
This qualitative description will frequently appear in the later algorithms for calculating geometric clutter, including judging whether the line segments intersect, polar angle sorting, convex hull problem and so on. Therefore, we must understand it thoroughly here.

Solution of two-dimensional convex hull problem

Application: two-dimensional convex hull can be used to solve fence problems, urban planning problems, cluster analysis (KMEANS clustering in machine learning: encircling similar classes with convex hull), etc.

1. Violence Act

All the points are corresponding in pairs, and then the remaining (n - 2) points are enumerated one by one to determine whether they are on the same side. If they are on the same side, that is, the two points are points on the convex hull.

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;
typedef unsigned long long ull;
struct Point{
    double x,y;
    bool ok;
}a[N];
int n;
stack<Point> s;
queue<Point> q;
int cross_product(Point a,Point b,Point c)
{
    if(a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - b.x * a.y - a.x * c.y > 0) return 1;
    else if(a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - b.x * a.y - a.x * c.y == 0) return 0;
    return -1;
}
void convex_hull()
{
    for(int i = 0;i < n;++i)
        for(int j = i + 1;j < n;++j){
            bool flag = true;
            int left = 0,right = 0;
            for(int k = 0;k < n;++k){
                if(k == i || k == j) ;
                else{
                    if(cross_product(a[i],a[j],a[k]) == 1) left++;
                    else if(cross_product(a[i],a[j],a[k]) == -1) right++;
                    if(left && right)    {flag = false;break;}
                }
            }
            if(flag)    a[i].ok = a[j].ok = true;
        }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> a[i].x >> a[i].y;
        a[i].ok = false;
    }
    convex_hull();
    for(int i = 0;i < n;++i)
        if(a[i].ok) cout << a[i].x << ' ' << a[i].y << endl;
    return 0;
}

2.Graham scanning method

First understand the order of the lower polar angle:
Polar angle
! [insert picture description here]( https://img-blog.csdnimg.cn/5d6e8746d8f44654b651d1d1ede2a043.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA4oitPQ==,size_20,color_FFFFFF,t_70,g_se,x_16Polar sorting
1. Using atan2 function

atan2(y,x) represents the line connecting the point (x,y) with the origin, and the included angle between the line and the positive half axis of the X axis. The range of the polar angle here is [− π, π], the first and second quadrants are positive, and the third and fourth quadrants are negative. Therefore, after sorting from small to large, it is actually the third quadrant → the fourth quadrant → the first quadrant → the second quadrant.

//Writing method I
bool cmp(Point a, Point b) {
    if(dcmp(atan2(a.y, a.x) - atan2(b.y, b.x)) == 0) //dcmp is a function to judge whether the floating point number is 0
        return a.x < b.x;
    return atan2(a.y, a.x) < atan2(b.y, b.x);
}
//Writing method 2
struct node{
    int x,y;
    double angle;
    inline bool operator < (const node &t) const{
        return angle<t.angle;
    }
}
for (int i=1;i<=n;i++){
    read(a[i].x),read(a[i].y);
    a[i].angle=atan2(a[i].y,a[i].x);
}
sort(a+1,a+n+1,cmp);

2. Sorting by vector cross multiplication

Given the two-point coordinates, the directed area of the triangle surrounded by the origin can be obtained by cross product.

For example, these two points are a and B
1 / 2 * (a.x * b.y − a.y * b.x) is the area of the triangle, so why is it a directed area? If this value is positive, it means that B is in the positive direction of a, that is, counterclockwise direction (of course, this angle is less than π). On the contrary, if this area is negative, it means that B is in the negative direction of a, that is, clockwise direction.
Then we can find the polar angle through the cross product.

struct node{
    int x,y;
    double angle;
    inline int operator * (const node &t) const{
        return a.x*b.y-a.y*b.x;
    } 
}
inline bool cmp(node a,node b){
    return a*b>0;
}
for (int i=1;i<=n;i++){
    read(a[i].x),read(a[i].y);
}
sort(a+1,a+n+1,cmp);

Idea: Graham's idea of scanning is to find a point on the convex hull first, and then find the points on the convex hull one by one counterclockwise from that point. In fact, it is to sort the polar angles, and then query and use them.
Time complexity: O(nlogn)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define PI 3.1415926535
using namespace std;
struct node
{
    int x,y;
};
node vex[1000];//All points stored
node stackk[1000];//All points in convex hull
int xx,yy;
bool cmp1(node a,node b)//Sort to find the first point
{
    if(a.y==b.y)
        return a.x<b.x;
    else
        return a.y<b.y;
}
int cross(node a,node b,node c)//Calculate cross product
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(node a,node b)//Calculate distance
{
    return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
}
bool cmp2(node a,node b)//Polar angle sorting is another method, which is fast
{
    if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
        return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
    return a.x<b.x;
}
bool cmp(node a,node b)//Polar sorting
{
    int m=cross(vex[0],a,b);
    if(m>0)
        return 1;
    else if(m==0&&dis(vex[0],a)-dis(vex[0],b)<=0)
        return 1;
    else return 0;
    /*if(m==0)
        return dis(vex[0],a)-dis(vex[0],b)<=0?true:false;
    else
        return m>0?true:false;*/
}
int main()
{
    int t,L;
    while(~scanf("%d",&t),t)
    {
        int i;
        for(i=0; i<t; i++)
        {
            scanf("%d%d",&vex[i].x,&vex[i].y);
        }
        if(t==1)
            printf("%.2f\n",0.00);
        else if(t==2)
            printf("%.2f\n",dis(vex[0],vex[1]));
        else
        {
            memset(stackk,0,sizeof(stackk));
            sort(vex,vex+t,cmp1);
            stackk[0]=vex[0];
            xx=stackk[0].x;
            yy=stackk[0].y;
            sort(vex+1,vex+t,cmp2);//cmp 2 is faster and cmp is easier to understand
            stackk[1]=vex[1];//The second point in the convex hull is stored in the structure of the convex hull
            int top=1;//Number of points in the last convex hull
            for(i=2; i<t; i++)
            {
                while(i>=1&&cross(stackk[top-1],stackk[top],vex[i])<0)   //Sometimes I > = 1 using polar sorting can not be used, but it is always good to add it
                    top--;
                stackk[++top]=vex[i];                                    //Control < 0 or < = 0 can control key points, collinear, depending on the topic.
            }
            double s=0;
            //For (I = 1; I < = top; I + +) / / output points on convex hull
            //cout<<stackk[i].x<<" "<<stackk[i].y<<endl;
            for(i=1; i<=top; i++)   //Calculate the perimeter of the convex hull
                s+=dis(stackk[i-1],stackk[i]);
            s+=dis(stackk[top],vex[0]);//The distance between the last point and the first point
            /*s+=2*PI*L;
            int ans=s+0.5;//rounding
            printf("%d\n",ans);*/
            printf("%.2lf\n",s);
        }
    }
}

3. Divide and Conquer

4. Jarvis March

5. Melkman algorithm

6. Incremental Method

7. Fast convex hull algorithm (Quick Hull)

8. Monotone Chain algorithm

9.Kirkpatrick – Seidel algorithm

10.chan algorithm

Solution of three-dimensional convex hull problem

1. Gift wrapping algorithm

2. Incremental algorithm

3. Fast convex hull algorithm

4. Divide and conquer algorithm

Research on higher dimensional convex hull problem

Reference link 1
Reference link 2
Reference link 3
Reference link 4