LeetCode每日一题刷题记录587.安装栅栏

看完题目毫无思路的一道题，想了想醉后还是看了官方题解，看完过后才发现这原来是个新的知识点，这类问题叫做包凸问题，题解里有三种方法分别是jarvis算法，andrew算法以及graham算法，我太菜了目前只写出来了jarvis算法，先说一下这个算法的大致原理

首先我可以先找到这堆树中最左边或者最右边的（最上最下应该也行）树（这里假设选取的是最左边的树），这棵树一定是在栅栏中的，然后我可以想象一根绕在树上的绳子如果想要将所有树都包进去的话，则这根绳子包绕到的下一颗树一定是顺时针方向最左或最右的树如图选取的就是绕顺时针方向最右的树，一旦选取了左右之后就不能再改变

这样不断找下去就可以找到所有点，原理非常简单但是代码写起来还是不那么容易（于我而言），有非常多的细节需要注意

class Solution 
{
    int cross(vector& p, vector& q, vector& r)
    {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }
    vector> ans;
    int length;
public:
    vector> outerTrees(vector>& trees) 
    {
        length = trees.size();
        //剪枝处理
        if (length <= 3)
            return trees;

        //找到最左树编号
        int mostLeft = 0;
        for (int i = 1; i < trees.size(); ++i)
        {
            if (trees[i][0] < trees[mostLeft][0])
                mostLeft = i;
        }

        //建立数组保存哪些树已使用
        vector used(length, false);

        int p = mostLeft;
        
        do
        {
            //如果p是之前在某条边上的点则不需要再加入答案
            if (!used[p])
            {
                used[p] = true;
                ans.push_back(trees[p]);
            }
            //找到最合适的q（相对p顺时针方向最右的点）
            int q = (p + 1) % length;
            for (int i = 0; i < length; ++i)
            {
                if (cross(trees[p], trees[q], trees[i]) < 0)
                {
                    q = i;
                }
            }

            //看有没有树在p和q之间
            for (int i = 0; i < length; ++i)
            {
                if (used[i] || i == p || i == q)
                    continue;
                if (cross(trees[p], trees[q], trees[i]) == 0)
                {
                    ans.push_back(trees[i]);
                    used[i] = true;
                }
            }
            p = q;
        } while (p != mostLeft);
        return ans;
    }
};

首先如何找到下一个点呢，可以利用叉积，两个点p和q形成一条直线，还有一个点r若再pq左侧则pq叉乘qr值为真，再右侧则为负，在pq上则为0，可以先随便找一个非p的点作为q的初值，一旦找到一个在pq右侧的点r就更新q的值为r，这样就能够找到下一个顺时针方向最右的点 

需要注意的是找到某一个点q过后，它与上一个点p之间的直线上可能存在其它点，这些点的叉积

为0，需要将这些点加入答案序列ans，但问题也随之而来，如果将某条边及延长线上的所有点都加入答案序列，如果下一个点又恰好是这条边延长线上的点会发生什么？会在ans中出现重复元素，因此需要一个数组记录哪些树用过，哪些树没用过同时在加入ans前进行判断