链接:https://ac.nowcoder.com/acm/contest/923/D
来源:牛客网

题目中隐含条件是给的图是一个 DAG,那么就是一个 DAG上求单源最短路的问题。首 先是肯定能写出一个 O ( n 2 ) O(n^2) O(n2)的 DP,然后因为每条边的边权是两个点之间的叉积。叉积的几何意义为有向面积的 2 2 2 倍。所以我们将所有向量画到直角坐标系中,并且按照极角排序,所求最短路就是让你选取平面中的若干个点,使得这个几何图形的面积最小。 y 均为正数,这个图形应该是越下凹面积越小使用单调栈维护这个下凹的凸壳,复杂 度可降为 O ( n ) O(n) O(n),处理时注意向量角相同的特征向量之间不能转移,需要特殊处理。

AC代码

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
const int maxn = 1e6+10;

inline int read() {
    int x=0, sign=1;
    char c=getchar();
    while((c<'0'||c>'9')&&c!='-') c=getchar();
    if(c=='-') sign=-1, c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
    return x*sign;
}

struct point{
    int x, y, id;
    point operator - (const point &b) const {
        return (point){x-b.x,y-b.y};
    }
    ll operator * (const point &b) const {
        return 1ll*x*b.y-1ll*y*b.x;
    }
    bool operator < (const point &b) const { //这个排序是从沿逆时针方向,且从外到内的排序
        if(*this*b==0) return y>b.y;
        return *this*b>0;
    }
};
int n, top; // top表示s数组元素的个数
ll ans[maxn], ANS; // ANS动态维护向下凹的图形的面积
point p[maxn], s[maxn]; // p数组代表排序后的点集;s数组代表构成的向下凹的图形的边界点集,其中一定包含了初始点,并且这个点集是动态的,至关重要。

int main() {
    memset(ans,-1,sizeof(ans));
    n=read();
    for(int i=1; i<=n; ++i) p[i]=(point){read(),read(),i};
    sort(p+1,p+1+n);
    int k=1, sta=read();
    while(k<=n&&p[k].id!=sta) ++k;
    s[top=1]=p[k];
    ans[sta]=0;
    while(k<=n&&p[k]*p[sta]==0) ++k; // 去掉与起始点极角相同的点
    for(int i=k; i<=n; ++i) {
        while(top>1&&(p[i]-s[top])*(p[i]-s[top-1])<=0) ANS-=s[top-1]*s[top], --top; // 由于当前点此刻必须要加进s中去,所以s数组中使得加入当前点后的图形变凸的点应该去掉。但这并不表明当前点能活多久,可能下一个i就会把当前点从s中去掉。
        s[++top]=p[i], ANS+=s[top-1]*s[top]; // 注意求面积要沿逆时针计算才是正数
        ans[p[i].id]=ANS;
    }
    for(int i=1; i<=n; ++i) printf("%lld\n", ans[i]);
}