学习心得——day3

啊~第三天了，前两天的总结还没写完……

今天接着昨天的斜率优化继续，具体介绍了叉积和下凸壳。

叉积是什么呢？叉积可是一个神奇的东西。

叉积也称为向量的外积，与内积不同，两个向量的外积依旧是一个向量，并且与这两个向量垂直。

那么叉积有什么用呢？跟斜率优化有什么关系呢？

•在平面几何中，可以用来判断两个向量的顺时针逆时针关系。

设A = [x1, y1] ,B = [x2, y2]

若x1 * y2 – x2 * y1 > 0，则B在A的逆时针方向，x1 * y2 – x2 * y1 < 0，则B在A的顺时针方向，x1 * y2 – x2 * y1 = 0，A与B平行。

有了叉积我们就可以判断一个新加入的节点是在当前最右节点的右上方还是右下方。

如图一：在图一的情况中，我们直接将新节点加入到凸壳中。

而图二中，我们应当删除最后一个元素。在每次删除之后，我们都还应继续比较删除后的最后一个节点。直到出现图一的情况。

 这里以一个例题的代码作为模板学习：

struct Vector
{
    LL x, y;
    Vector() {}
    Vector(LL _x, LL _y)
    {
        x = _x; y = _y;
    }
    Vector operator -(const Vector &a) const
    {
        return Vector(x - a.x, y - a.y);
    }
} que[N];

LL cross(Vector a, Vector b)//叉积判断新节点与末节点的位置关系
{
    return a.x * b.y - a.y * b.x;
}

int head, tail;
void add(Vector p)
{
    while(tail - head >= 2)//队列中存在至少两个节点
    {
        if(cross(que[tail - 1] - p, que[tail - 2] - p) < 0) break;
        --tail;
    }
    que[tail++] = p;
}

而对于查询，我们每次找到相同斜率下，截距最小的点作为结果返回。

LL cal(Vector p, LL k) //计算需要求出的值
{
    return p.y - k * p.x;
}

LL read(LL k)
{
    while(head + 1 < tail)
    {
        if(cal(que[head], k) < cal(que[head + 1], k)) break;//找到第一个权值大于当前点的位置，根据单调性，所有更靠右的点的权值都大于当前改点
        ++head;
    }
    return cal(que[head], k);
}

 （……正在施工……）