汕头市队赛 SRM14 T1 计算几何瞎暴力

计算几何瞎暴力

(easy.pas/c/cpp) 128MB 1s

在平面上，给定起点和终点，有一面墙（看作线段）不能穿过，问从起点走到终点的最短路程。

输入格式

输入一行，包含8个用空格分隔的整数xS,yS,xT,yT,x1,y1,x2,y2，依次表示起点(xS,yS)，终点(xT,yT)，线段(x1,y1)-(x2,y2)。

输出格式

输出一个整数，表示答案四舍五入到整数后的值，保证答案精确值的小数点后一位不是4或5。

样例输入

1 1 2 2 1 2 2 1

样例输出

2

样例解释

走折线(1,1)-(1,2)-(2,2)或(1,1)-(2,1)-(2,2)路程最短。

数据范围

对30%的数据，xS<=xT<=x1<=x2

对所有的数据，输入的整数在范围1..1000内，保证起点和终点不在线段上

————————————————————————————————————

这道题判一下线段是否和起点终点连线想交就好了

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=2e4+,inf=0x3f3f3f3f;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,l,ans;

int sum[M],w[M],f[][M],mx;

int q[M],ql,qr,k;

int F(int x){return f[k-][x]-sum[x];}

int main(){

    freopen("hard.in","r",stdin);

    freopen("hard.out","w",stdout);

    n=read(); m=read(); l=read();

    for(int i=l;i<n+l;++i) w[i]=read();

    n=n+*l-;

    for(int i=;i<=n;++i) sum[i]=sum[i-]+w[i];

    for(int i=;i<l;++i) f[][i]=-inf;

    for(int i=l;i<=n;++i) f[][i]=sum[i]-sum[i-l];

    for(k=;k<=m;++k){

        ql=,qr=;

        mx=-inf;

        for(int i=;i<l;++i) f[k][i]=-inf;

        for(int i=l;i<=n;++i){

            while(ql<=qr&&q[ql]<=i-l) ++ql;

            while(ql<=qr&&F(q[qr])<=F(i-)) --qr;

            q[++qr]=i-;

            mx=max(mx,f[k-][i-l]);

            f[k][i]=max(mx+sum[i]-sum[i-l],F(q[ql])+sum[i]);

        }

    }

    ans=;

    for(int i=;i<=m;++i)

        for(int j=l;j<=n;++j) ans=max(ans,f[i][j]);

    printf("%d\n",ans);

    return ;

}