根据光路最快原理以及斯涅尔定律,可以得到从定点$P$进入某条直线的最佳入射角。

求出每个端点到每条线段的最佳点,建图求最短路即可。

时间复杂度$O(n^2\log n)$。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<double,int>PI;
const int N=2100000,M=9100000;
const double eps=1e-6,inf=1e100;
int n,cnt,i,j,g[N],v[M],nxt[M],ed;double w[M],d[N],va,vb,si[2],co[2];
priority_queue<PI,vector<PI>,greater<PI> >q;
inline void add(int x,int y,double z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
inline void add2(int x,int y,double z){add(x,y,z),add(y,x,z);}
inline void ext(int x,double y){if(y+eps<d[x])q.push(PI(d[x]=y,x));}
inline int sgn(double x){
if(x>eps)return 1;
if(x<-eps)return -1;
return 0;
}
struct P{
double x,y;
P(){}
P(double _x,double _y){x=_x,y=_y;}
P operator+(P b){return P(x+b.x,y+b.y);}
P operator-(P b){return P(x-b.x,y-b.y);}
P operator*(double b){return P(x*b,y*b);}
P operator/(double b){return P(x/b,y/b);}
double operator*(P b){return x*b.x+y*b.y;}
bool operator==(P b){return !sgn(x-b.x)&&!sgn(y-b.y);}
double len(){return hypot(x,y);}
P rotate(double s,double c){return P(x*c-y*s,x*s+y*c);}
P rot90(){return P(-y,x);}
}a[1010];
struct E{
double x;int y;
E(){}
E(double _x,int _y){x=_x,y=_y;}
}e[2010];
inline bool cmp(const E&a,const E&b){return a.x<b.x;}
inline double cross(P a,P b){return a.x*b.y-a.y*b.x;}
inline bool point_on_segment(P p,P a,P b){
return sgn(cross(b-a,p-a))==0&&sgn((p-a)*(p-b))<=0;
}
inline P line_intersection(P a,P b,P p,P q){
double U=cross(p-a,q-p),D=cross(b-a,q-p);
return a+(b-a)*(U/D);
}
inline void work(int st,int en){
int i,j,m=2;
P A=a[st],B=a[en],C=(B-A).rot90();
e[1]=E(0,st),e[2]=E(C.len(),en);
for(i=0;i<=n;i++)if(i!=st&&i!=en)for(j=0;j<2;j++){
P D=line_intersection(A,B,a[i],a[i]+C.rotate(si[j],co[j]));
if(D==A||D==B)continue;
if(!point_on_segment(D,A,B))continue;
cnt++;
add2(i,cnt,(a[i]-D).len()/vb);
e[++m]=E((D-A).len(),cnt);
}
sort(e+1,e+m+1,cmp);
for(i=1;i<m;i++)add2(e[i].y,e[i+1].y,(e[i+1].x-e[i].x)/va);
}
int main(){
scanf("%d%lf%lf",&n,&va,&vb);
for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
if(sgn(va-vb)<=0)return printf("%.10f",(a[0]-a[n]).len()/vb),0;
si[0]=vb/va;
co[0]=sqrt(1.0-si[0]*si[0]);
si[1]=-si[0];
co[1]=co[0];
cnt=n;
for(i=0;i<=n;i++)for(j=0;j<i;j++)add2(i,j,(a[i]-a[j]).len()/vb);
for(i=0;i<n;i++)work(i,i+1);
for(i=0;i<=cnt;i++)d[i]=inf;
ext(0,0);
while(!q.empty()){
PI t=q.top();q.pop();
if(t.first-eps>d[t.second])continue;
for(i=g[t.second];i;i=nxt[i])ext(v[i],t.first+w[i]);
}
return printf("%.10f",d[n]),0;
}

  

最新文章

  1. Java批处理ExecutorService/CompletionService
  2. jQuery基本操作
  3. DBMS_JOBS
  4. 简要地写出一个.NET&#160;Remoting的示例
  5. AVC1与H264的差别
  6. 关于Xcode7的HTTP请求不到网络的问题
  7. c#中override重写和new隐藏
  8. 如何定义AIDL跨进程间通信
  9. leetcode第13题--Roman to Integer
  10. winform .net2.0的程序如何运行于.net 4.x
  11. 历史命令~/.bash_history,查看所有别名alias,命令执行顺序,命令行常用快捷键,输入输出重定向,wc统计字节单词行数
  12. WebAPI 实现前后端分离
  13. 【c的文件操作】文本文件和二进制文件(内存映像)的不同 文件结尾判断feof , EOF
  14. Java对象模型规约
  15. Spring AOP功能和目标
  16. ORM一对多增加记录
  17. docker-ce-17.09 数据卷和数据卷容器
  18. c# List&lt; int&gt;和List&lt; string&gt;互相转换
  19. Heapify
  20. Docker: 如何将node.js的项目部署到docker的swarm上面去

热门文章

  1. gitlab使用--汉化及修改端口
  2. 数据库和linux对大小写的区分
  3. MySQL表按月切割
  4. 开始写博客,学习Linq
  5. [转] js在浏览器端对二进制流进行AES加密和解密
  6. [WC2014]紫荆花之恋
  7. Codeforces 935E Fafa and Ancient Mathematics dp
  8. React 入门实例教程(转载)
  9. 数学模型:3.非监督学习--聚类分析 和K-means聚类
  10. day4 字符串的操作