hdu 4445 Crazy Tank(枚举视角)

hdu 4445 Crazy Tank(枚举角度)

这题第一反映肯定是三分角度，然后求最大值。。但是有友方坦克的存在，如果一个角度会导致某个导弹打到友方坦克，那么返回结果直接是0。

所以只能萎缩地枚举角度了。。。。e中保存地方坦克的区间，f中保存友方坦克的区间。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<sstream>
#include<vector>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
#define MP make_pair
#define eps 1e-8
using namespace std;

const double PI = acos(-1);
const double g = 9.8;
const int maxn = 222;
int n;
double v[maxn];
double l, r, l1, l2, r1, r2, H, a, b;

struct Seg
{
    double l, r;
};
vector<Seg> e, f;

template <class T> T sqr(T x){ return x*x; }
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}

bool check1(double m)
{
    REP(i, e.size())
    {
        double a=e[i].l, b=e[i].r;
        if(dcmp(m-a)>=0 && dcmp(b-m)>=0) return true;
    }
    return false;
}

bool check2(double m)
{
    REP(i, f.size())
    {
        double a=f[i].l, b=f[i].r;
        if(dcmp(m-a)>=0 && dcmp(b-m)>=0) return true;
    }
    return false;
}

int calc(double ang)
{
    int ret = 0;
    REP(i, n)
    {
        double vy = -v[i]*sin(ang);
        double vx = v[i]*cos(ang);
        double t = vx * ((sqrt(sqr(vy)+2*H*g)-vy) / g);
        if(check1(t)) ret++;
        if(check2(t)) return 0;
    }
    return ret;
}

int main()
{
    while(~scanf("%d", &n), n)
    {
        e.clear(); f.clear();
        scanf("%lf%lf%lf%lf%lf", &H, &l1, &r1, &l2, &r2);
        REP(i, n) scanf("%lf", &v[i]);
        if(dcmp(l1-r2) > 0 || dcmp(l2-r1) > 0)
        {
            e.PB((Seg){l1, r1});
            f.PB((Seg){l2, r2});
        }
        else if(dcmp(l1-l2) > 0 && dcmp(r2-l1) >= 0 && dcmp(r1-r2) >= 0)
        {
            e.PB((Seg){r2, r1});
            f.PB((Seg){l2, r2});
        }
        else if(dcmp(r2-r1) > 0 && dcmp(l2-l1) >= 0 && dcmp(r1-l2) >= 0)
        {
            e.PB((Seg){l1, l2});
            f.PB((Seg){l2, r2});
        }
        else if(dcmp(l2-l1)>=0 && dcmp(r1-l2)>=0 && dcmp(r2-l1)>=0 && dcmp(r1-r2)>=0)
        {
            e.PB((Seg){l1, l2});
            e.PB((Seg){r2, r1});
            f.PB((Seg){l2, r2});
        }
        else
        {
            e.PB((Seg){l1, r1});
            f.PB((Seg){l2, r2});
        }

        double L = -PI/2, R = PI/2;
        int ans = 0;


        while(L + eps < R)
        {
            L += PI/1000.0;
            int k = calc(L);
            ans = max(ans, k);
        }

        printf("%d\n", ans);
    }
    return 0;
}