记录编号	416887	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]智能车大赛	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2017-06-22 21:55:35	内存使用	6.39 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long double db;
const int N=1e5+10;
const db pi=acos(-1.0),eps=1e-12;
struct line{int x,l,r,id;}p[N];
bool cmp(const line &x,const line &y){
	return x.x==y.x?x.id<y.id:x.x<y.x;
}
int n,l[N],r[N],pos[N];
db dis[N],x[N],y[N];
db sqr(db x){return x*x;}
db dist(int i,int j){return sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));}
int main()
{
	freopen("noi2011_car.in","r",stdin);
	freopen("noi2011_car.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d%*d%d",&pos[i],&l[i],&r[i]);
	for (int i=2;i<=n;i++)
		p[i]=(line){pos[i],max(l[i],l[i-1]),min(r[i],r[i-1]),i};
	int xs,ys,xt,yt;db v;
	scanf("%d%d%d%d%Lf",&xs,&ys,&xt,&yt,&v);
	if (xs>xt) swap(xs,xt),swap(ys,yt);
	p[1]=(line){xs,ys,ys,1};
	p[n+1]=(line){xt,yt,yt,n+1};
	sort(p+1,p+n+2,cmp);
	for (int i=1;i<=n+1;i++){
		x[i<<1]=p[i].x;
		x[i<<1|1]=p[i].x;
		y[i<<1]=p[i].l;
		y[i<<1|1]=p[i].r;
		if (p[i].id==1) dis[i<<1]=dis[i<<1|1]=0;
			else dis[i<<1]=dis[i<<1|1]=1e9;
	}
	for (int i=2;i<=n*2+3;i++){
		db right=pi/2,left=-pi/2;
		for (int j=i/2+1;j<=n+1;j++){
			if (p[j].x!=p[i/2].x){
				right=min(right,atan2(p[j].r-y[i],p[j].x-x[i]));
				left=max(left,atan2(p[j].l-y[i],p[j].x-x[i]));
			}
			if (right+eps<left) break;
			int k=j<<1;
			db phi=atan2(y[k]-y[i],x[k]-x[i]);
			if (phi>=left-eps&&phi<=right+eps)
				dis[k]=min(dis[k],dis[i]+dist(i,k));
			k++;
			phi=atan2(y[k]-y[i],x[k]-x[i]);
			if (phi>=left-eps&&phi<=right+eps)
				dis[k]=min(dis[k],dis[i]+dist(i,k));
		}
	}
	for (int i=1;i<=n+1;i++)
		if (p[i].id==n+1) return printf("%.12Lf\n",dis[i<<1]/v),0;
	return 0;
}