[2016北京集训测试赛3]masodik-[凸包]

Description

Soluton

666这道题竟然用凸包。。。

维护r和c的下凸壳。哪个斜率大走哪个。

证明：我们先不考虑其他的，只考虑两条路，如下图：

设图的长度为x，宽度为y。如果我们要走上面的路径，则r1*y+c1*x>=r2*y+c2*x。

移项得$frac{(r1-r2)}{x}geq frac{(c2-c1)}{y}$。

显然对于只有两条路的情况，证明成立。

感性理解一下，最终的最优路径必然是由无数点的最优路径组成，如S->T1->T2->T3->T4。。。->T

所以，我就厚着脸皮认为它成立啦。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
int r[100010],c[100010],qr[100010],topr=0,qc[100010],topc=0;
int tpr,tpc;
long long ans;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n;i++)
    {
        scanf("%d",&r[i]);
        while (topr>1&&1ll*(r[i]-r[qr[topr]])*(qr[topr]-qr[topr-1])<1ll*(r[qr[topr]]-r[qr[topr-1]])*(i-qr[topr])) topr--;
        qr[++topr]=i;
    }
    for (int i=0;i<=m;i++)
    {
        scanf("%d",&c[i]);
        while (topc>1&&1ll*(c[i]-c[qc[topc]])*(qc[topc]-qc[topc-1])<1ll*(c[qc[topc]]-c[qc[topc-1]])*(i-qc[topc])) topc--;
        qc[++topc]=i;
    }
    tpr=tpc=1;
    while (tpr<topr&&tpc<topc)
    {
        if (1ll*(r[qr[tpr+1]]-r[qr[tpr]])*(qc[tpc+1]-qc[tpc])<=1ll*(c[qc[tpc+1]]-c[qc[tpc]])*(qr[tpr+1]-qr[tpr]))
        ans+=1ll*(qr[tpr+1]-qr[tpr])*c[qc[tpc]],tpr++;
        else ans+=1ll*(qc[tpc+1]-qc[tpc])*r[qr[tpr]],tpc++;
    }
    if (tpr==topr) ans+=1ll*(m-qc[tpc])*r[n];else ans+=1ll*(n-qr[tpr])*c[m];
    cout<<ans;
}