注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2433][Noi2011]智能车比赛  

2015-01-20 13:51:59|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2433: [Noi2011]智能车比赛

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 654  Solved: 340
[Submit][Status]

Description

 新一届智能车大赛在JL大学开始啦!比赛赛道可以看作是由n个矩形区域拼接而成(如下图所示),每个矩形的边都平行于坐标轴,第i个矩形区域的左下角和右上角坐标分别为(xi,1,yi,1)和(xi,2,yi,2)。

题目保证:xi,1<xi,2=xi+1,1,且yi,1< yi,2,相邻两个矩形一定有重叠在一起的边(如图中虚线所示),智能车可以通过这部分穿梭于矩形区域之间。

选手们需要在最快的时间内让自己设计的智能车从一个给定的起点S点到达一个给定的终点T点,且智能车不能跑出赛道。假定智能车的速度恒为v且转向不消耗任何时间,你能算出最快需要多少时间完成比赛么?

Input

 输入的第一行包含一个正整数n,表示组成赛道的矩形个数。
接下来n行描述这些矩形,其中第i行包含4个整数xi,1, yi,1, xi,2, yi,2,表示第i个矩形左下角和右上角坐标分别为(xi,1, yi,1)和(xi,2, yi,2)。
接下来一行包含两个整数xS, yS,表示起点坐标。
接下来一行包含两个整数xT, yT,表示终点坐标。
接下来一行包含一个实数v,表示智能车的速度。

Output

 仅输出一个实数,至少精确到小数点后第六位,为智能车完成比赛的最快时间。

对于每个测试点,如果你的输出结果和参考结果相差不超过10^-6,该测试点得满分,否则不得分。

Sample Input

2
1 12 2
203 4
1 1
30
1.0

Sample Output

2.41421356

HINT

N<=2000,所输入数字为绝对值小于40000的整数

Solution

先把矩形的条件变成从点S到点T,只能从若干条竖着的线段里边经过。

对于每一条线段,我们考虑它的两个端点对后面的答案造成的影响(S和T可以看成一条长度为0的线段)。当我们要以这个点来更新后面的点的答案(最多只有O(n)个)时,维护当前点最高能看到哪里和最低能看到哪里(就是视界线),如果当前目标点可以被看到,那么一定可以沿直线到达这个点。

Code

/**************************************************************
    Problem: 2433
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:16 ms
    Memory:976 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#define ld double
ld max(ld a,ld b){return a>b?a:b;}
ld min(ld a,ld b){return a<b?a:b;}
struct P{ld x,y;}tmp,rg[2010][2];
#define PP const P&
P operator+(PP a,PP b){return (P){a.x+b.x,a.y+b.y};}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
P operator*(PP a,ld p){return (P){a.x*p,a.y*p};}
P operator/(PP a,ld p){return (P){a.x/p,a.y/p};}
ld cross(PP a,PP b){return a.x*b.y-a.y*b.x;}
ld len(PP a){return sqrt(a.x*a.x+a.y*a.y);}
int aa;int F(){return scanf("%d",&aa),aa;}
P s,t;int n,i,j,k,ns,nt,pre[2010];double v,f[2010][2];
struct R{P l,r;}a[2010];
bool ckin(ld l,ld r,ld x){return l<=x&&x<=r;}
void calc(P a,int i,double ret){
    P l=a-(P){0,1},r=a+(P){0,1};
    for(;i<=nt&&cross(rg[i][0]-a,r-a)>=0&&cross(l-a,rg[i][1]-a)>=0;i++){
        if(cross(l-a,rg[i][0]-a)>=0){
            l=rg[i][0];
            f[i][0]=min(f[i][0],ret+len(a-rg[i][0]));
        }
        if(cross(rg[i][1]-a,r-a)>=0){
            r=rg[i][1];
            f[i][1]=min(f[i][1],ret+len(a-rg[i][1]));
        }
    }
}
int main(){
    for(n=F(),i=1;i<=n;i++)a[i]=(R){(P){F(),F()},(P){F(),F()}};
    s=(P){F(),F()},t=(P){F(),F()};scanf("%lf",&v);s.x+=1e-9,t.x+=1e-9;
    if(s.x>t.x)tmp=s,s=t,t=tmp;
    for(ns=1;!ckin(a[ns].l.x,a[ns].r.x,s.x);ns++);ns--;
    if(t.x>=a[n].r.x)nt=n;
    else for(nt=n;nt>=1&&!ckin(a[nt].l.x,a[nt].r.x,t.x);nt--);a[nt].r.x=t.x;
    for(i=ns+1;i<nt;i++){
        rg[i][0]=(P){a[i].r.x,max(a[i].l.y,a[i+1].l.y)};
        rg[i][1]=(P){a[i].r.x,min(a[i].r.y,a[i+1].r.y)};
    }
    s.x-=1e-9,t.x-=1e-9;
    rg[ns][0]=rg[ns][1]=s;
    rg[nt][0]=rg[nt][1]=t;
    for(i=ns+1;i<=nt;i++)f[i][0]=f[i][1]=1e100;
    calc(s,ns+1,0);
    for(i=ns+1;i<nt;i++){
        calc(rg[i][0],i+1,f[i][0]);
        calc(rg[i][1],i+1,f[i][1]);
    }
    printf("%.6lf\n",max(f[nt][0],f[nt][1])/v);
}
  评论这张
 
阅读(264)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018