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

ydc的博客

 
 
 

日志

 
 

bzoj 2596 疯狂赛车  

2014-01-07 21:21:35|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 LaTex不会搞图片……所以还是手写吧
看到题大家都应该知道……难点在于路径有无数条所以唯一的做法是找出关键点和关建边构图并跑最短路了
反正我是毫无头绪……所以滚去看唐文斌的题解了
虽然唐文斌的做法讲的很详细了……但那个证明却一点都不详细T_T
我是知道了怎么证明之后才看懂他的证明的

虽然题目没说va>=vb,但数据都是va>=vb的。另外若va<vb直接输出即可

考虑这么一个问题bzoj 2596 疯狂赛车 - ydc - ydc的博客
 求P到B的最短路
显然只有两种可能,直接P->B,P到AB上一点C到B
作P到AB的投影P',设P'C=x,并设P'B=Lbzoj 2596 疯狂赛车 - ydc - ydc的博客
 容易得到函数关系式f(x)=sqrt(h^2+x^2)/vb+(L-x)/va。对f(x)求导并解方程容易得到一个极值点
由于f'(x)函数式里没有常数L,所以说明了,只要L足够大,最优点一定!
对于L小到最优点跑到线段外直线上了的特殊情况,由于f‘(x)在这一段>0,所以PB就是最优解了
当然……由于对称性,C关于P'的对称点C'是P到A的最优点!

做法如下:
所有端点直接连通过沙漠走到的边
枚举每个点P,每条边AB,求出P关于AB的最优点P',P与P'连沙漠边
求出每条边AB上的所有最优点,顺带加上AB,相邻点连赛道边
跑Heap+Dijkstra

现在是证明
定义:
关键点:通过上述算法构造出来的点
AB(赛道):一条赛道线段,端点是AB
AB(沙漠):一条沙漠线段,端点是AB
Tab(赛道):AB(赛道)花费时间
Tab(沙漠):AB(沙漠)花费时间
twb的证明……不管神犇看没看懂,表示我个傻叉是没看懂的(虽然现在懂了)
化学课向ljc大神请教了好久……数学课的时候他发现了一个很屌的性质,暂且称为ljc引理(学vfk的题解风范 )
bzoj 2596 疯狂赛车 - ydc - ydc的博客
从A到B的话,一定要走我们构图得到的关键点构成的路径。
证明如下:
反证法
唯一的反例只可能长这样

 bzoj 2596 疯狂赛车 - ydc - ydc的博客
 EF是线段的另外两个端点了……然后反例是A->C->D->B,然后C或者D不是关键点
过A,E做CD的平行线交BF于A'和E'两点,显然AA'和EE'必有一条线段<=CDbzoj 2596 疯狂赛车 - ydc - ydc的博客
 现在是EE'<=CD,我们作E'C'∥ECbzoj 2596 疯狂赛车 - ydc - ydc的博客
 AC(赛道)和E'B(赛道)抵掉,EE'(沙漠)和CC'(沙漠)抵掉,现在证明Tec(赛道)<Tc'd(沙漠)+Tde'(赛道)
∵va>=vb ∴Tc'd(沙漠)>=Tc'd(赛道)
根据三角形两边之和大于第三边,容易得到Tc'e'(赛道)<Tc'd(赛道)+Tde'(赛道)<Tc'd(沙漠)+Tde'(赛道)
所以在这个例子中,最优方案一定是A->E->BF上某点->B
神奇的发现,这个BF上某点是定的——一定是E在BF上的最优点——也就是关键点!

有了ljc引理,接下来数学归纳法就好做了。
和数学组的HTM大神讨论了一下,以下简称HTM定理:
对于任意两个线段,从一个走到另一个都一定要那么走……
将其扩充成三个线段bzoj 2596 疯狂赛车 - ydc - ydc的博客
假设AG->GH->HI->IF最优
我们发现……如果把G给定住,那么转化为GD和EF的最短路……这就是二维线段情况!
于是H是定点!!无论G如何移动,只要GH足够长,H是不变的。当然GH很短的时候例外,但那个时候的最优点仍然是一个关键点啊
同理,如果H定住,G也是定点!他也是关键点!

有种很神奇的感觉……我相信这是一个很严谨的证明但是我讲的很奇葩
大概意思就是……GH是定点,而且还一定是关键点。
于是直接上数学归纳法,就有了TWB(唐文斌)定理:
WC2007的疯狂赛车是用以上方法做的

一些题外话:
ljc得到了ljc引理后大胆断言以下算法:枚举点P线段AB,P到B最优点是P',将P->P'->B的代价当做PB的边权……用如下方法构图,跑不堆优化的Dijkstra,时间复杂度O(n^2)
然后他就没管了……那个时候还没有问到HTM定理……所以我就大胆的写了一个程序……40分
反例很显然只要那三个线段的I和F重合就是一个反例了……不过这个不是题意里的折线……所以还要多构造一下
另外我还90分WA on test 7了好久,因为我逗逼的以为枚举P和线段AB后P的投影一定得在AB上才有那个解……后来猛然发现自己的逗逼之后很不爽的求出最优点再判断是否在线段上,果然是人傻

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define maxn 3000010
#define maxm 1010
#define eps 1e-10
#define each(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
using namespace std;
int dcmp(double p)
{
if(abs(p)<eps)
return 0;
return p>eps?1:-1;
}
struct Point
{
double x,y;
Point() {}
Point(double x,double y): x(x),y(y) {}
friend Point operator + (Point a,Point b)
{
return Point(a.x+b.x,a.y+b.y);
}
friend Point operator - (Point a,Point b)
{
return Point(a.x-b.x,a.y-b.y);
}
friend Point operator * (Point a,double p)
{
return Point(a.x*p,a.y*p);
}
friend Point operator / (Point a,double p)
{
return Point(a.x/p,a.y/p);
}
friend bool operator < (Point a,Point b)
{
return dcmp(a.x-b.x)<0||(!dcmp(a.x-b.x)&&dcmp(a.y-b.y)<0);
}
friend bool operator != (Point a,Point b)
{
return dcmp(a.x-b.x)||dcmp(a.y-b.y);
}
friend bool operator == (Point a,Point b)
{
return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);
}
void Read()
{
scanf("%lf %lf",&x,&y);
}
}p[maxm];
typedef Point Vector;
double Cross(Vector a,Vector b)
{
return a.x*b.y-a.y*b.x;
}
double Dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
double Len(Vector a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
Point Shadow(Point p,Point a,Point b)
{
Vector v=b-a;
double t=-Dot(a-p,v)/Dot(v,v);
return a+v*t;
}
double Len(Point a,Point b,Point c)
{
return abs(Cross(b-a,c-a)/Len(c-b));
}
struct Edge
{
int v;
double cost;
Edge() {}
Edge(int v,double cost): v(v),cost(cost) {}
};
vector<Edge> adj[maxn];
struct Node
{
int p;
double dis;
Node() {}
Node(int p,double dis): p(p),dis(dis) {}
friend bool operator < (const Node &a,const Node &b)
{
return a.dis>b.dis;
}
};
priority_queue<Node> Q;
int n,nPoint;
double va,vb;
void read()
{
scanf("%d",&n);
scanf("%lf %lf",&va,&vb);
p[++nPoint]=Point(0,0);
for(int i=1;i<=n;++i)
p[++nPoint].Read();
for(int i=1;i<=nPoint;++i)
for(int j=1;j<=nPoint;++j)
if(i!=j)
adj[i].push_back(Edge(j,Len(p[j]-p[i])/vb));
}
bool OnSegment(Point a,Point b,Point c)
{
return dcmp(a.x-b.x)*dcmp(a.x-c.x)<=0&&dcmp(a.y-b.y)*dcmp(a.y-c.y)<=0;
}
void makegraph()
{
vector<Point> Event;
static int pos[maxm*2];
for(int i=1;i<=n;++i)
{
Event.clear();
Point a=p[i],b=p[i+1];
for(int j=1;j<=n+1;++j)
if(p[j]!=a&&p[j]!=b)
{
double h=Len(p[j],a,b);
double x=vb*h/sqrt(va*va-vb*vb);
Point pa=Shadow(p[j],a,b);
Vector v;
Point c;
v=(b-a)/Len(b-a);
c=pa+v*x;
if(OnSegment(c,a,b))
Event.push_back(c);
v=(a-b)/Len(a-b);
c=pa+v*x;
if(OnSegment(c,a,b))
Event.push_back(c);
}
Event.push_back(a),Event.push_back(b);
sort(Event.begin(),Event.end());
int N=unique(Event.begin(),Event.end())-Event.begin();
if(Event[0]==a)
pos[0]=i,pos[N-1]=i+1;
else
pos[0]=i+1,pos[N-1]=i;
for(int j=1;j<N-1;++j)
pos[j]=++nPoint;
for(int j=0;j<N-1;++j)
{
adj[pos[j]].push_back(Edge(pos[j+1],Len(Event[j+1]-Event[j])/va));
adj[pos[j+1]].push_back(Edge(pos[j],Len(Event[j+1]-Event[j])/va));
}
for(int j=1;j<=n+1;++j)
if(p[j]!=a&&p[j]!=b)
{
double h=Len(p[j],a,b);
double x=vb*h/sqrt(va*va-vb*vb);
Point pa=Shadow(p[j],a,b);
Vector v;
Point c;
v=(b-a)/Len(b-a);
c=pa+v*x;
if(OnSegment(c,a,b))
{
int id=lower_bound(Event.begin(),Event.end(),c)-Event.begin();
adj[j].push_back(Edge(pos[id],Len(p[j]-c)/vb));
adj[pos[id]].push_back(Edge(j,Len(p[j]-c)/vb));
}
v=(a-b)/Len(a-b);
c=pa+v*x;
if(OnSegment(c,a,b))
{
int id=lower_bound(Event.begin(),Event.end(),c)-Event.begin();
adj[j].push_back(Edge(pos[id],Len(p[j]-c)/vb));
adj[pos[id]].push_back(Edge(j,Len(p[j]-c)/vb));
}
}
}
}
double Dijkstra(int S,int T)
{
static double dis[maxn];
static bool use[maxn];
Q.push(Node(S,0));
for(int i=1;i<=nPoint;++i)
dis[i]=1<<30;
while(!Q.empty())
{
Node p=Q.top();
Q.pop();
if(use[p.p])
continue;
use[p.p]=true;
each(i,adj[p.p])
if(dis[i->v]>p.dis+i->cost)
{
dis[i->v]=p.dis+i->cost;
Q.push(Node(i->v,dis[i->v]));
}
}
return dis[T];
}
int main()
{
read();
makegraph();
printf("%f\n",Dijkstra(1,n+1));
return 0;
}


  评论这张
 
阅读(605)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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