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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2433][Noi2011]智能车比赛  

2015-06-23 11:15:17|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2433: [Noi2011]智能车比赛

注意细节……

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long double ld;
const double eps = 1e-9;
const int N = 2000+100;
struct Point{double x,y;Point(double a=0,double b=0){x=a;y=b;}
void init(){cin >> x >> y;}}S,E;
Point operator + (const Point&a,const Point&b){return Point(a.x+b.x,a.y+b.y);}
Point operator - (const Point&a,const Point&b){return Point(a.x-b.x,a.y-b.y);}
Point operator * (const Point&a,double b){return Point(a.x*b,a.y*b);}
Point operator / (const Point&a,double b){return Point(a.x/b,a.y/b);}
double Dot(const Point&a,const Point&b){return a.x*b.x + a.y*b.y;}
double Length(const Point&a){return sqrt(Dot(a,a));}
int n,m,from[N][2];
double V,f[N][2];
Point rect[N];double xi[N];
double Rad(const Point&a){
return atan2(a.y,-a.x);
}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
cin >> n;
for(i=1;i<=n;i++){
Point p;
p.init();
rect[i].x = p.y;
p.init();
rect[i].y = p.y;
xi[i] = p.x;
if(i > 1){
rect[i-1].x = max(rect[i-1].x,rect[i].x);
rect[i-1].y = min(rect[i-1].y,rect[i].y);
}
}
S.init();E.init();
cin >> V;
Point p[2];
//update f
for(i=1;xi[i] <= E.x+eps && i<=n;i++){
Point now;
f[i][0] = f[i][1] = 1e50;
if(xi[i] <= S.x+eps)continue;
double l,r,tl,tr;
l = -M_PI/2;
r = +M_PI/2;
now = Point(xi[i],rect[i].x);
for(j=i-1;xi[j] > S.x+eps && j;j--){
p[0] = Point(xi[j],rect[j].x);
p[1] = Point(xi[j],rect[j].y);
tl = Rad(p[0] - now);
tr = Rad(p[1] - now);
if(l<=tl+eps && tl<=r+eps){
f[i][0] = min(f[i][0],Length(p[0]-now)+f[j][0]);
if(fabs(f[i][0]-(Length(p[0]-now)+f[j][0])) < eps){
from[i][0] = -j;
}
}
if(l<=tr+eps && tr<=r+eps){
f[i][0] = min(f[i][0],Length(p[1]-now)+f[j][1]);
if(fabs(f[i][0]-(Length(p[1]-now)+f[j][1])) < eps){
from[i][0] = +j;
}
}
l = max(tl,l);
r = min(tr,r);
if(l > r)break;
}
tl = Rad(S-now);
if(l <= tl+eps && tl <= r+eps){
f[i][0] = min(f[i][0],Length(now-S));
if(fabs(f[i][0] - Length(now-S)) < eps){
from[i][0] = 0;
}
}

l = -M_PI/2;
r = +M_PI/2;
now = Point(xi[i],rect[i].y);
for(j=i-1;xi[j] > S.x+eps && j;j--){
p[0] = Point(xi[j],rect[j].x);
p[1] = Point(xi[j],rect[j].y);
tl = Rad(p[0] - now);
tr = Rad(p[1] - now);
if(l<=tl+eps && tl<=r+eps){
f[i][1] = min(f[i][1],Length(p[0]-now)+f[j][0]);
if(fabs(f[i][1]-(Length(p[0]-now)+f[j][0])) < eps){
from[i][1] = -j;
}
}
if(l<=tr+eps && tr<=r+eps){
f[i][1] = min(f[i][1],Length(p[1]-now)+f[j][1]);
if(fabs(f[i][1]-(Length(p[1]-now)+f[j][1])) < eps){
from[i][1] = +j;
}
}
l = max(tl,l);
r = min(tr,r);
if(l > r)break;
}
tl = Rad(S-now);
if(l <= tl+eps && tl <= r+eps){
f[i][1] = min(f[i][1],Length(now-S));
if(fabs(f[i][1] - Length(now-S)) < eps){
from[i][1] = 0;
}
}
}

//update End_Point
double ans = 1e50;
double l,r,tl,tr;
l = -M_PI/2;
r = +M_PI/2;

for(j=i-1;j;j--){
p[0] = Point(xi[j],rect[j].x);
p[1] = Point(xi[j],rect[j].y);
tl = Rad(p[0] - E);
tr = Rad(p[1] - E);
if(fabs(p[0].x-E.x) < eps && fabs(p[0].y-E.y) < eps)
tl = l;
if(fabs(p[1].x-E.x) < eps && fabs(p[1].y-E.y) < eps)
tr = r;
if(l<=tl+eps && tl<=r+eps){
ans = min(ans,Length(p[0]-E)+f[j][0]);
}
if(l<=tr+eps && tr<=r+eps){
ans = min(ans,Length(p[1]-E)+f[j][1]);
}
l = max(tl,l);
r = min(tr,r);
if(l > r)break;
}
tl = Rad(S-E);
if(l <= tl+eps && tl <= r+eps){
ans = min(ans,Length(E-S));
}
printf("%.10f\n",ans/V);
return 0;
}

题解:
可以注意到最优路线一定是以矩形顶点为关键点的折线
然后DP
for i in 1..n
for j in i-1..1
随着j的减小维护一个未被挡住的弧度区间
复杂度N^2
需要注意的地方:
[BZOJ2433][Noi2011]智能车比赛 - 时光机 - 时光机TimeMachine(红色是终点)这样的情况不能处理的话只有60分……
 
  评论这张
 
阅读(59)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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