圈水池（凸包）

古城微笑少年丶 2022-08-01 06:21 166阅读 0赞

![20150621143709068][]

**这一题就是让你找凸包的点，最基础的凸包问题，可是感觉还是**

**很难！先发一下代码！**

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<stack>
    using namespace std;
    struct A
    {
        int x;
        int y;
    }s[105],s1[105];
    int fun(A a1,A a2)
    {
        if(a1.y==a2.y)
        {
            return a1.x<a2.x;
        }
        else
        {
            return a1.y<a2.y;
        }
    }//排序函数先找y值最小的那个！如果相同，则找x值最小的那个！
    int fun2(A a1,A a2)
    {
        if(a1.x==a2.x)
        {
            return a1.y<a2.y;
        }
        else
        {
            return a1.x<a2.x;
        }
    }
    bool fp(A a1,A a2,A a3)
    {
        return (a2.x-a1.x)*(a3.y-a1.y)>(a3.x-a1.x)*(a2.y-a1.y);
        //这个说明a2a1在a1a3的相对方向！
        //结果为正为顺时针方向，结果为0为逆时针方向！
        //即return值为0时为逆时针方向,则说明要去掉a2点增加a3点！
    }
    int main()
    {
        int t,n,i,top;
        cin>>t;
        while(t--)
        {
            cin>>n;
            for(i=0;i<n;i++)
            {
                cin>>s[i].x>>s[i].y;
            }
            sort(s,s+n,fun);
            s1[0]=s[0];s1[1]=s[1];top=1;
            for(i=2;i<n;i++)
            {
                while(top&&!fp(s1[top],s1[top-1],s[i]))
                {
                    top--;//去掉s1[top]
                }
                 s1[++top]=s[i];//增加新点！
                //这里应该有一个回溯!但是省略了，为什么有回溯，想想就知道！
            }
            //所以后面就是一个回溯！
            int h=top;s1[++top]=s[n-2];
            //想一下,此时s1[top]=s[m-2],s1[top-1]=s[m-1];
            for(i=n-3;i>=0;i--)
            {
                while(top!=h&&!fp(s1[top],s1[top-1],s[i]))
                {
                    top--;
                }
                //这里,如果s1[top-1]s1[top]相对于s1[top-1]s[i]逆时针
                s1[++top]=s[i];
            }
            sort(s1,s1+top,fun2);
            for(int i=0;i<top;i++)
            {
                cout<<s1[i].x<<" "<<s1[i].y<<endl;
            }
        }
    }

**我想说一下为什么需要回溯？**

**![20150621144324829][]**

![20150621144330175][]

![20150621144336219][]

![20150621144340985][]

![20150621144345169][]

![Center][]

[20150621143709068]: /images/20220731/8fd81ad66dd5440b86e7ebcecd093308.png
[20150621144324829]: /images/20220731/5028736f539f48aebadcb64dc1dd2309.png
[20150621144330175]: /images/20220731/3fd65c71b9f04abaaae3b9a310ef71ea.png
[20150621144336219]: /images/20220731/aa5c8c88944d4b68b351a8253cd66b43.png
[20150621144340985]: /images/20220731/75d684ace8ab4920b8e23eae04b87cd0.png
[20150621144345169]: /images/20220731/ad42bc3b292a4c9089c5bd38661bab4d.png
[Center]: /images/20220731/92a262fa32e041a3a32b5e721eba2d96.png