首页 > ACM题库 > HDU-杭电 > HDU 4445-Crazy Tank-分治-[解题报告]HOJ
2015
07-16

HDU 4445-Crazy Tank-分治-[解题报告]HOJ

Crazy Tank

问题描述 :

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.
Walk

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.

输入:

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.

输出:

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.

样例输入:

2
10 10 15 30 35
10.0
20.0
2
10 35 40 2 30
10.0
20.0
0

样例输出:

1
0
Hint
In 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].

题意:在高为H的台上有一个坦克向右打炮,[L1.R1]为敌军范围,[L2,R2]为友军范围,现在有n(0<=n<=200)个初速度不同的炮弹,现在想找到一个最好的

         角度使得任意一个不打在友军的范围内同时打在敌军最多。

题解:对于不同的炮弹打的最远的角度是不一样的,因为这个我wa的很惨。对于每个炮弹三分找出能打最远的角度,然后枚举打的点分别为L1.R1,L2,R2,

         二分得到两个角度更新答案。

         PS:个人认为出题者的本意不应该是暴力枚举角度吧……


Sure原创,转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <cmath>
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int maxn = 202;
const double g = 9.80;
const double eps = 1e-8;
const double PI = acos(-1.0);
double pos[10],v[maxn];
double h,farest;
int n;

void read()
{
    scanf("%lf %lf %lf %lf %lf",&h,&pos[0],&pos[1],&pos[2],&pos[3]);
    for(int i=0;i<n;i++)
    {
        scanf("%lf",&v[i]);
    }
    return;
}

double dis(double ang,double vv)
{
    double s = sin(ang);
    double c = cos(ang);
    return vv * s * (vv * c + sqrt(vv * vv * c * c + 2.0 * g * h)) / g;
}

void tris(double vv)
{
    double l = 0,r = PI / 2.0;
    int t = 30;
    while(t--)
    {
        double mid = (l + r) / 2.0;
        double midd = (l + mid) / 2.0;
        if(dis(midd , vv) > dis(mid , vv)) r = mid;
        else l = midd;
    }
    farest = l;
    return;
}

double bis_left(double l,double r,double d,double vv)
{
    int t = 30;
    while(t--)
    {
        double mid = (l + r) / 2.0;
        if(dis(mid , vv) <= d) l = mid;
        else r = mid;
    }
    return l;
}

double bis_right(double l,double r,double d,double vv)
{
    int t = 30;
    while(t--)
    {
        double mid = (l + r) / 2.0;
        if(dis(mid , vv) < d) r = mid;
        else l = mid;
    }
    return l;
}

void solve()
{
    int res = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<4;j++)
        {
            tris(v[i]);
            if(dis(farest , v[i]) < pos[j]) continue;
            double wei = pos[j];
            if(j == 0) wei += eps;
            if(j == 1) wei -= eps;
            if(j == 2) wei -= eps;
            if(j == 3) wei += eps;
            double ang = bis_left(0.0 , farest , wei , v[i]);
            bool flag = true;
            int c = 0;
            for(int k=0;k<n;k++)
            {
                double here = dis(ang , v[k]);
                if(here >= pos[2] && here <= pos[3])
                {
                    flag = false;
                    break;
                }
                else if(here >= pos[0] && here <= pos[1]) c++;
            }
            if(flag) res = MAX(res , c);
            if(res == n) break;

            ang = bis_right(farest , PI , wei , v[i]);
            flag = true;
            c = 0;
            for(int k=0;k<n;k++)
            {
                double here = dis(ang , v[k]);
                if(here >= pos[2] && here <= pos[3])
                {
                    flag = false;
                    break;
                }
                else if(here >= pos[0] && here <= pos[1]) c++;
            }
            if(flag) res = MAX(res , c);
            if(res == n) break;
        }
    }
    printf("%d\n",res);
    return;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        read();
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/flying_stones_sure/article/details/8134930