做电脑系统网站,如何进行企业营销型网站建设规划,个人做外贸网站违法吗,动漫制作专业就业形势题目描述
Description 新一届智能车大赛在JL大学开始啦#xff01;比赛赛道可以看作是由n个矩形区域拼接而成#xff08;如下图所示#xff09;#xff0c;每个矩形的边都平行于坐标轴#xff0c;第i个矩形区域的左下角和右上角坐标分别为(xi,1,yi,1)和(xi,2,yi,2)。 题目…题目描述
Description 新一届智能车大赛在JL大学开始啦比赛赛道可以看作是由n个矩形区域拼接而成如下图所示每个矩形的边都平行于坐标轴第i个矩形区域的左下角和右上角坐标分别为(xi,1,yi,1)和(xi,2,yi,2)。 题目保证xi,1xi,2xi1,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 有精度误差请不要提交 N2000,所输入数字为绝对值小于40000的整数 Source day1 分析
就是求一个最短路这条路肯定是从左到右的我们可以用 DP DP来求。 我们先预处理出矩形之间的交点显然智能车只能经过起点、终点和这些点。 加上起点在终点左边如果不是交换一下位置 然后 O(n2)DP O(n^2)DP在 DP DP过程中记录一下当前点能够向后到达的点的斜率范围就可以了。 dist[j]minmink≤ki,j≤maxk(dist[j],dist[i]Di,j)
dist[j]=\min_{mink\le k_{i,j}\le maxk}(dist[j],dist[i]+D_{i,j}) 代码
#includecstdio
#includealgorithm
#includecmath
#includecstring
#define y1 myi
using namespace std;
#define MAXN 2000
int n,cnt,sx,sy,ex,ey,x1[MAXN10],x2[MAXN10],y1[MAXN10],y2[MAXN10];
double v,dist[MAXN*210];
void Read(int x){static char c;bool f(0);while(cgetchar(),c!EOF){if(c-)f1;else if(c0c9){xc-0;while(cgetchar(),c0c9)xx*10c-0;ungetc(c,stdin);if(f)x-x;return;}}
}
void read(){Read(n);for(int i1;in;i)Read(x1[i]),Read(y1[i]),Read(x2[i]),Read(y2[i]);Read(sx),Read(sy),Read(ex),Read(ey);if(sxex)swap(sx,ex),swap(sy,ey);scanf(%lf,v);
}
struct point{int x,y;inline point(){}inline point(int x,int y):x(x),y(y){}
}a[MAXN*210];
void prepare(){a[cnt]point(sx,sy);int t[4],i;for(i1;in;i){if(sxx2[i])continue;if(exx2[i])break;t[1]y1[i],t[2]y2[i],t[3]y1[i1],t[0]y2[i1];sort(t,t4);a[cnt]point(x2[i],t[1]);a[cnt]point(x2[i],t[2]);}a[cnt]point(ex,ey);
}
inline double sqr(double x){return x*x;
}
void solve(){int i,j;double mxk,mik,k;for(i2;icnt;i)dist[i]1e20;for(i1;icnt;i){mxk1e20,mik-1e20;for(ji1;jcntmikmxk;j)if(a[i].xa[j].x)dist[j]min(dist[j],dist[i]abs(a[i].y-a[j].y));else{k1.0*(a[j].y-a[i].y)/(a[j].x-a[i].x);if(mikkkmxk)dist[j]min(dist[j],dist[i]sqrt(sqr(a[j].y-a[i].y)sqr(a[j].x-a[i].x)));if(j1)mxkmin(mxk,k);elsemikmax(k,mik);}}
}
int main()
{read();prepare();solve();printf(%.10lf\n,dist[cnt]/v);
}
