国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > UVA11796- Dog Distance

UVA11796- Dog Distance

来源:程序员人生   发布时间:2014-09-30 07:55:45 阅读次数:3084次

题意是给出两条轨迹,分别给出起点和终点,要求两条轨迹同时开始跑,同时到达重点


问,中途两点间最大距离和最小距离的差值


我的做法:


设一个速度,用向量法模拟过程


我的代码:

#include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; const double inf=1e9; struct dot { double x,y; dot(){} dot(double a,double b){x=a;y=b;} dot operator +(dot a){return dot(x+a.x,y+a.y);} dot operator -(dot a){return dot(x-a.x,y-a.y);} dot operator *(double a){return dot(x*a,y*a);} double operator *(dot a){return x*a.y-y*a.x;} dot operator /(double a){return dot(x/a,y/a);} double operator /(dot a){return x*a.x+y*a.y;} bool operator ==(dot a){return x==a.x&&y==a.y;} void in(){scanf("%lf%lf",&x,&y);} void out(){printf("%lf %lf",x,y);} double mod(){return sqrt(x*x+y*y);} double dis(dot a){return sqrt(pow(x-a.x,2)+pow(y-a.y,2));} }; double mxd(dot a,dot b,dot c) { return max(a.dis(b),a.dis(c)); } double mnd(dot a,dot b,dot c) { if((a-b)/(c-b)<=0) return a.dis(b); if((a-c)/(b-c)<=0) return a.dis(c); return fabs((a-b)*(c-b)/b.dis(c)); } int main() { double va,vb,mx,mn; dot a[110],b[110],sa,sb,s,e,ta,tb,v,t; int i,j,T,TT,n,m; cin>>T; for(TT=1;TT<=T;TT++) { mx=0; mn=inf; cin>>n>>m; for(i=0;i<n;i++) a[i].in(); va=0; for(i=1;i<n;i++) va+=a[i-1].dis(a[i]); for(i=0;i<m;i++) b[i].in(); vb=0; for(i=1;i<m;i++) vb+=b[i-1].dis(b[i]); sa=a[0];sb=b[0]; i=j=1; while(i<n&&j<m) { ta=a[i]-sa; ta=ta/ta.mod(); ta=ta*va; tb=b[j]-sb; tb=tb/tb.mod(); tb=tb*vb; if(sa.dis(a[i])/va>sb.dis(b[j])/vb) { v=tb-ta; t=sa; s=sb; e=s+v*(sb.dis(b[j])/vb); sa=sa+ta*(sb.dis(b[j])/vb); sb=b[j++]; } else { v=ta-tb; t=sb; s=sa; e=s+v*(sa.dis(a[i])/va); sb=sb+tb*(sa.dis(a[i])/va); sa=a[i++]; } mx=max(mx,mxd(t,s,e)); mn=min(mn,mnd(t,s,e)); } printf("Case %d: %.0lf ",TT,mx-mn); } }

原题:

Download as PDF


 

C

Dog Distance

Input

Standard Input

Output

Standard Output

Two dogs, Ranga and Banga, are running randomly following two different paths. They both run for T seconds with different speeds. Ranga runs with a constant speed of R m/s, whereas Banga runs with a constant speed of S m/s. Both the dogs start and stop at the same time. Let D(t) be the distance between the two dogs at time t.

The dog distance is equal to the difference between the maximum and the minimum distance between the two dogs in their whole journey.

 

Mathematically,

Dog Distance = {max (D(a)) 0 <= a <= T}

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生