题解

2 条题解

  • 0

    题解这不就来了?
    这道题第一眼看的时候,感觉可能是计算几何判断线段合法+最短路跑图,可是后来仔细一看题目的给的数据保证矩形是从左往右的(即第i个矩形的右界与第i+1个矩形的左界重合), 而且很容易就能够看出,通过两点之间线段最短说明路程一定是折线或线段,如果是折线的话拐点一定是位于矩形的顶点,与此同时拐点位于重合的边上,那么每个矩形产生两个点,这一张联通图最多只有(2*N+2)个点,时间复杂度为O(n²),期望得分:100分。 那么要怎么算出最优解,我就想到了DP(因为矩形一定是从左到右的),F[i]表示起点到点i的最短距离,轻松写出状态转移式:F[i]=min(F[i],F[j]+len(i,j))(线段ij合法)。判断合法的方法,我们选择用两个向量表示范围,那么过程中我们只要通过斜率去维护这个范围就行了。 附上代码:
    ```cpp
    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<math.h>
    #include<cmath>
    using namespace std;
    int a[10],n,stx,sty,edx,edy,num;
    int x1[2010],ydown[2010],x2[2010],y2[2010];
    double v,dis[4010];
    struct node{
    int x;int y;
    }p[5005];
    void saw()
    {
    num=1;p[1].x=stx;p[1].y=sty;
    for (int i=1;i<n;i++)
    {
    if (stx>x2[i]) continue;

    if (x2[i]>edx) break;
    a[1]=ydown[i],a[2]=y2[i],a[3]=ydown[i+1],a[4]=y2[i+1];
    sort(a+1,a+1+4);
    num++;
    p[num].x=x2[i];
    p[num].y=a[2];
    num++;
    p[num].x=x2[i];
    p[num].y=a[3];
    }
    num++;
    p[num].x=edx;
    p[num].y=edy;
    }
    int main()
    {
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    scanf("%d%d%d%d",&x1[i],&ydown[i],&x2[i],&y2[i]);
    scanf("%d%d%d%d",&stx,&sty,&edx,&edy);
    if (stx>edx)
    {
    swap(stx,edx);
    swap(sty,edy);
    }
    scanf("%lf",&v);

    saw();
    for (int i=2;i<=num;i++) dis[i]=1e99;
    for (int i=1;i<num;i++)
    {
    double nox=(double)p[i].x*1.0;
    double noy=(double)p[i].y*1.0;
    double mmax=1e99;
    double mmin=-1e99;
    for (int j=i+1;j<=num;j++)
    {
    double len;
    double nex=(double)p[j].x*1.0;
    double ney=(double)p[j].y*1.0;

    if (nex==nox)
    {
    len=abs(ney-noy);
    dis[j]=min(dis[j],len+dis[i]);
    continue;
    }
    double tmp=(ney-noy)/(nex-nox);
    if ((tmp<=mmax)&&(tmp>=mmin))
    {
    double hh=(ney-noy)*(ney-noy)+(nex-nox)*(nex-nox);
    len=sqrt(hh);
    dis[j]=min(dis[j],len+dis[i]);
    }
    if ((j%2)==0) mmin=max(mmin,tmp);
    else mmax=min(mmax,tmp);
    }
    }
    double ans=dis[num]/v;
    printf("%.10lf\n",ans);
    }
    ```

  • 0
    @ 2015-08-04 21:34:08

    一个也没有???!!!......

  • 1

信息

ID
1804
难度
7
分类
(无)
标签
递交数
94
已通过
18
通过率
19%
被复制
1
上传者