HDU 5826 physics （积分推导）

physics

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5826

Description

There are n balls on a smooth horizontal straight track. The track can be considered to be a number line. The balls can be considered to be particles with the same mass. At the beginning, ball i is at position Xi. It has an initial velocity of Vi and is moving in direction Di.(Di∈−1,1) Given a constant C. At any moment, ball its acceleration Ai and velocity Vi have the same direction, and magically satisfy the equation that Ai * Vi = C. As there are multiple balls, they may collide with each other during the moving. We suppose all collisions are perfectly elastic collisions. There are multiple queries. Each query consists of two integers t and k. our task is to find out the k-small velocity of all the balls t seconds after the beginning. * Perfectly elastic collision : A perfectly elastic collision is defined as one in which there is no loss of kinetic energy in the collision.

Input

The first line contains an integer T, denoting the number of testcases. For each testcase, the first line contains two integers n <= 10^5 and C <= 10^9. n lines follow. The i-th of them contains three integers Vi, Xi, Di. Vi denotes the initial velocity of ball i. Xi denotes the initial position of ball i. Di denotes the direction ball i moves in. The next line contains an integer q <= 10^5, denoting the number of queries. q lines follow. Each line contains two integers t <= 10^9 and 1<=k<=n. 1<=Vi<=10^5,1<=Xi<=10^9

Output

For each query, print a single line containing the answer with accuracy of 3 decimal digits.

Sample Input

1 3 7 3 3 1 3 10 -1 2 7 1 3 2 3 1 2 3 3

Sample Output

6.083 4.796 7.141

Source

2016 Multi-University Training Contest 8
##题意：在一条无限长水平直轨道上有n个相同的球，给出每个球的初速度、起始位置、方向. 给出若干询问，每次输出 t 秒时第 k 小的速度是多少. 对任意球的任一时刻而言，速度与加速度同方向，且它们的乘积为定值C.
##题解：由于是变加速度运动，肯定要用积分来解决. 微元法：考虑一段极小的时间间隔：dt. 速度增量为 dv . 则： ![](http://images2015.cnblogs.com/blog/764119/201608/764119-20160811175239356-2092410654.png) 化简为 ![](http://images2015.cnblogs.com/blog/764119/201608/764119-20160811175256668-1857027472.png) 两边同时积分：dv的积分区间为[v0, v], dt的积分区间为[0, t]. 那么结果为：![](http://images2015.cnblogs.com/blog/764119/201608/764119-20160811175059152-232557318.png)
关于小球的位置和方向：由于是完全弹性碰撞，碰撞的双方会交换速度，这就等同于忽视碰撞. 所以题目中的初位置和方向都没用. 关于小球速度的大小关系：任意时刻初速度大的都比初速度小的大. 反证：某一时刻，A的速度大于B，则A的加速度就小于B，一段时间后A和B速度相同且拥有相同的加速度. 所以B的速度永远不会超过A.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 101000 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

double v[maxn];

int main(int argc, char const *argv[])
{
//IN;

int t; cin >> t;
while(t--)
{
    double C; int n;
    scanf("%d %lf", &n, &C);

    for(int i=1; i<=n; i++) {
        int a,b; scanf("%lf %d %d", &v[i], &a,&b);
    }
    sort(v+1, v+1+n);

    int q; scanf("%d", &q);
    while(q--) {
        int pos; double t; scanf("%lf %d", &t, &pos);
        double ans = v[pos]*v[pos] + 2.0*C*t;
        ans = sqrt(ans);
        printf("%.3f
", ans);
    }
}

return 0;

}