数学题 追及相遇—HDOJ1275 人傻需要多做题

两车追及或相遇问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1145    Accepted Submission(s): 353

Problem Description

外号叫“猪头三”的小学生在数学课上，经常遇到两车相遇或追及的方程题，经过长时间的练习，他发现了许多规律，然而他不懂计算机，他想请你帮忙编写一个计算机程序，解决他的问题。
题
目的描述是这样的：甲、乙两地相距L公里，A车的速度为VA公里/小时，B车的速度为VB公里/小时，A车和B车开始时分别在甲、乙两地，现在两车同时从
甲、乙两地出发，并且开始计时，两车到达甲、乙两地后返回继续行驶，这样会有许多次追及或相遇的时候，我们假定称追及或相遇的时候为“重合”，请输出“重
合”时的时间以及离甲、乙两地较近地的距离。

 

Input

本题有多个测试数据组，第一行为测试数据组数N，接着是N行数据，每行的数据按顺序分别为实数类型的距离、A车的速度、B车的速度以及整数类型的第几次“重合”的序号数(<=1000)。

 

Output

Time=xxxx.xxx Dist=xx.xxx输出的精度为精确到小数点后三位。

 

Sample Input

2
120.7 90.0 90.0 10
100.5 80.7 69.3 1

 

Sample Output

Time=12.741 Dist=60.350
Time=0.670 Dist=46.431

 

我们注意到重合序号最多一千 即相遇最多1000次 追击也1000次

我们可以考虑相遇 第一次相遇 两者直接碰面 时间L/(a+b)

第一次追及 L/|a-b|

下一次相遇或追击两者路程相差L的倍数

而下一次相遇和追击 方向保持初始追击/相遇的状态

 当多走L的偶数倍时 AB方向保持初始追击/相遇的状态

故重合时间 总是（2*i+1）*L/(a+b)或者（2*i+1）*L/|a-b|

#include<cstdio>

#include<map>

//#include<bits/stdc++.h>

#include<vector>

#include<stack>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<cstdlib>

#include<climits>

#define PI acos(-1.0)

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

typedef __int64 int64;

const ll mood=1e9+;

const int64 Mod=;

const double eps=1e-;

const int N=2e7+;

const int MAXN=;

typedef int rl;

inline void r(rl&num){

    num=;rl f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<='')num=num*+ch-'',ch=getchar();

    num*=f;

}

double L,a,b;int ci;

void init()

{

    scanf("%lf%lf%lf%d",&L,&a,&b,&ci);

}

double t[MAXN];

int main()

{

    int T;

    r(T);

    while(T--)

    {

        init();

        double tem=fabs(a-b),te=a+b;

        for(int i=;i<;i++)

        {

            t[*i]=(*i+)*L/tem;

            t[*i+]=(*i+)*L/te;

        }

        sort(t,t+);

        double x=t[ci-];

        double y=t[ci-]*a;

        y-=floor(y/L)*L;

        y=min(y,fabs(L-y));

        printf("Time=%.3f Dist=%.3f\n",x,y);

    }

    return ;

}