UVA11796- Dog Distance
來源：程序員人生 發布時間：2014-09-30 07:55:45 閱讀次數：3523次
題意是給出兩條軌跡，分別給出起點和終點，要求兩條軌跡同時開始跑，同時到達重點
問，中途兩點間最大距離和最小距離的差值
我的做法：
設一個速度，用向量法模擬過程
我的代碼：
#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);
}
}
原題：
|
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}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
------分隔線----------------------------
------分隔線----------------------------