hdu4445 Crazy Tank
Crazy Tank
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6106 Accepted Submission(s): 1328
Problem Description
Crazy Tank was a famous game about ten years ago. Every child liked it. Time flies, children grow up, but the memory of happy childhood will never go.
Now you’re controlling the tank Laotu on a platform which is H meters above the ground. Laotu is so old that you can only choose a shoot angle(all the angle is available) before game start and then any adjusting is not allowed. You need to launch N cannonballs and you know that the i-th cannonball’s initial speed is Vi.
On the right side of Laotu There is an enemy tank on the ground with coordination(L1, R1) and a friendly tank with coordination(L2, R2). A cannonball is considered hitting enemy tank if it lands on the ground between [L1,R1] (two ends are included). As the same reason, it will be considered hitting friendly tank if it lands between [L2, R2]. Laotu's horizontal coordination is 0.
The goal of the game is to maximize the number of cannonballs which hit the enemy tank under the condition that no cannonball hits friendly tank.
The g equals to 9.8.
Now you’re controlling the tank Laotu on a platform which is H meters above the ground. Laotu is so old that you can only choose a shoot angle(all the angle is available) before game start and then any adjusting is not allowed. You need to launch N cannonballs and you know that the i-th cannonball’s initial speed is Vi.
On the right side of Laotu There is an enemy tank on the ground with coordination(L1, R1) and a friendly tank with coordination(L2, R2). A cannonball is considered hitting enemy tank if it lands on the ground between [L1,R1] (two ends are included). As the same reason, it will be considered hitting friendly tank if it lands between [L2, R2]. Laotu's horizontal coordination is 0.
The goal of the game is to maximize the number of cannonballs which hit the enemy tank under the condition that no cannonball hits friendly tank.
The g equals to 9.8.
Input
There are multiple test case.
Each test case contains 3 lines.
The first line contains an integer N(0≤N≤200), indicating the number of cannonballs to be launched.
The second line contains 5 float number H(1≤H≤100000), L1, R1(0<L1<R1<100000) and L2, R2(0<L2<R2<100000). Indicating the height of the platform, the enemy tank coordinate and the friendly tank coordinate. Two tanks may overlap.
The third line contains N float number. The i-th number indicates the initial speed of i-th cannonball.
The input ends with N=0.
Each test case contains 3 lines.
The first line contains an integer N(0≤N≤200), indicating the number of cannonballs to be launched.
The second line contains 5 float number H(1≤H≤100000), L1, R1(0<L1<R1<100000) and L2, R2(0<L2<R2<100000). Indicating the height of the platform, the enemy tank coordinate and the friendly tank coordinate. Two tanks may overlap.
The third line contains N float number. The i-th number indicates the initial speed of i-th cannonball.
The input ends with N=0.
Output
For each test case, you should output an integer in a single line which indicates the max number of cannonballs hit the enemy tank under the condition that no cannonball hits friendly tank.
Sample Input
2 10 10 15 30 35 10.0 20.0 2 10 35 40 2 30 10.0 20.0 0
Sample Output
1 0HintIn the first case one of the best choices is that shoot the cannonballs parallelly to the horizontal line, then the first cannonball lands on 14.3 and the second lands on 28.6. In the second there is no shoot angle to make any cannonball land between [35,40] on the condition that no cannonball lands between [2,30].
这题刚看到的时候是一脸懵逼,后来想了想根据速度求出当前速度要打到friend tank 的角度,然后求出区间和,也就是这个区间不能选,然后再分别求出每个炮弹要打到enemy tank 的角度,然后求重叠区间,这样应该是可行的,但是有点太麻烦啦,估计很难写出来;
然后想了想枚举角度,因为最大位置会是一个区间,所以只要分的细就能枚举出来这里炮弹只有200个不会超时;
ac 代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
double h,l1,r1,l2,r2;
const double PI=2*asin(1.0);
const double g=9.8;
int n;
double v[205];
int get_ans(double x)
{
int ans=0;
for(int i=0;i<n;i++)
{
double l=(v[i]*v[i]*sin(x)*cos(x)+v[i]*cos(x)*sqrt(v[i]*v[i]*sin(x)*sin(x)+2*g*h))/g;
if(l>=l2&&l<=r2)
return 0;
if(l<=r1&&l>=l1)
ans++;
}
return ans;
}
int main()
{
while(cin>>n&&n)
{
cin>>h>>l1>>r1>>l2>>r2;
for(int i=0;i<n;i++)
cin>>v[i];
int ans=0;
for(double i=-PI/2;i<=PI/2;i+=PI/1000)
ans=max(get_ans(i),ans);
cout<<ans<<endl;
}
return 0;
}