本蒟蒻的凸包实现的详细解释

· · 题解 

/*
本蒟蒻知道本题各位大神给出了各种各样的神奇做法qwq
但还是决定把这题的代码的每一步的意思详细的给初学凸包解释一遍
你们珂以在看完Graham的证明之后却没有什么思路的情况下来看qwq
而各位大佬，这只是蒟蒻的一篇题解，在您看完之后有什么意见或发现什么问题
请一定告知本人，本人一定会认真修改，谢谢。
*/
#include<bits/stdc++.h>
using namespace std;
struct EE{
    double x,y,dis,dus;//x,y坐标,dis向量,dus度数。 
}e[10001],s[10001];//e初始坐标，s凸包的坐标 
double ans;//答案
double qx=100000000,qy=100000000;//初始位置 
bool cmp(EE a,EE b)
{
    return a.dus<b.dus;//先按度数把每个点排下序 
}
int main()
{
    int n,qd,js=0;//qd初始点的位置，也就是我们找的那个凸出来的点 。
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i].x>>e[i].y;
        if(e[i].y<qy||(e[i].y==qy&&e[i].x<qx))//寻找初始点 
        {
            qd=i;//记录初始点信息 
            qx=e[i].x;
            qy=e[i].y;
        }
    }
    for(int i=1;i<=n;i++)
    {
        e[i].x-=qx;
        e[i].y-=qy;//以初始点为坐标原点（方便求角度） 
        if(e[i].x==0&&e[i].y==0)
            e[i].dus=0;//初始点 
        else if(e[i].x!=0)
            e[i].dus=atan2(e[i].y,e[i].x)*180/acos(-1);//套上算角度的模板qwq 
        else 
            e[i].dus=90;//垂直的 
        e[i].dis=e[i].x*e[i].x+e[i].y*e[i].y;//套上求向量的模板qwq 
    }
    swap(e[1],e[qd]);//把初始点放到队首 
    sort(e+1+1,e+n+1,cmp);//先按度数把其他每个点排下序 
    e[++n]=e[1];//最后凸包会绕一圈回到初始点 
    s[++js]=e[1];
    s[++js]=e[2];//这俩个点一定在凸包上 
    ans=sqrt((e[2].x-e[1].x)*(e[2].x-e[1].x)+(e[2].y-e[1].y)*(e[2].y-e[1].y));//先计算着俩点之间的距离（勾股定理--a*a+b*b=c*c） 
    for(int i=3;i<=n;i++)// 从未知的第三个点开始做 
    {
        while(js>=2)//当队列里有俩个和俩个以上的点开始找下一个凸包上的点 （其实while(1)也行，因为刚开始的俩个点一定在凸包上） 
        {//关键来了 （神奇的做法） 
            double pd=(e[i].x-s[js-1].x)*(s[js].y-s[js-1].y)-(s[js].x-s[js-1].x)*(e[i].y-s[js-1].y);
            // 神奇的向量做法本蒟蒻并不知道原理 只会套模板qwq 
            if(pd>0)//当pd大于0的时候 ，说明这我们的队列的最后（应该叫栈的栈顶才对qwq）的点不在凸包上 
            {
                js--;//把这个无用的点踢出队列（栈） 
                ans-=sqrt((s[js+1].x-s[js].x)*(s[js+1].x-s[js].x)+(s[js+1].y-s[js].y)*(s[js+1].y-s[js].y));
                //减去他的长度（贡献） 然后再次判断新的栈顶在不在凸包上 
            }
            else//表示现在栈顶在凸包上qwq，恭喜咋们可以停止踢点了 
                break;
        }
        s[++js]=e[i];//把我们新连接的点放入我们的栈中，再加上它的长度（贡献） 
        ans+=sqrt((s[js].x-s[js-1].x)*(s[js].x-s[js-1].x)+(s[js].y-s[js-1].y)*(s[js].y-s[js-1].y));
    }
    //最后，经过九九八十一的磨难，我们回到了初始点，算出了答案qwq 
    printf("%0.2lf\n",ans);//保留俩位小数 
}
/*
本人的做法可能和很多代码相似，主要是因为模板的原因，本人的代码参考了jzqjzq的博客专栏qwq
再次感谢qwq
*/