学步园

2012 Multi-University Training Contest 8

1009题

转载请注明出处：http://blog.csdn.net/CyberZHG

题意：

一个半径为R的星球上，有n个外星人，每两个外星人可以制造一个圆，这个圆以球心为圆心，过两个外星人中点。

人类逃跑的速度为h * k * vo，h是距离外星人的圆的距离，k和vo都是常数。

有m组询问，问人类逃离到离圆最远点所需要的时间。

微积分+线性代数+解析几何

首先要把球坐标转换为直角坐标：

\left\{\begin{matrix}
x =& r sin\theta cos\phi \\ 
y =& r sin\theta sin\phi \\ 
z =& r cos\theta
\end{matrix}\right.

后面可以看出，r是没有实际作用的，完全不用管。

由于人在球上行动，且速度一直变化，所以这是一个积分的过程。

设人到最远点的球面角度为α，则

kv_{0}h = kv_{0}cos\alpha

α可以由向量的点乘积确定，圆的法向量与两个外星人连线方向相同，人的向量的方向是人与球心的连线方向。

\alpha = arccos(\frac{v1 \cdot v2}{|v1| \cdot |v2|})

为了最近，α大于π/2时要用π减去α。

\begin{align}
T &= \int_{\alpha}^{0} \frac{-dR\theta}{kv_{0}Rcos\theta} \nonumber \\
  &= \frac {1}{kv_{0}} \int_{0}^{\alpha} \frac {d\theta}{cos\theta} \nonumber \\
  &= \frac {1}{kv_{0}} \int_{0}^{\alpha} sec\theta \nonumber
\end{align}

考虑右边的积分

\begin{align}
\int_{0}^{\alpha}sec\theta d\theta &= \int_{0}^{\alpha} \frac{d\theta}{cos\theta}\nonumber \\
&= \int_{0}^{\alpha} \frac{cos\theta}{cos^{2}\theta}d\theta \nonumber \\
&= \int_{0}^{\alpha} \frac{d(sin\theta)}{1 - sin^{2}\theta} \nonumber \\
&= \int_{0}^{\alpha} \frac{d(sin\theta)}{(1 + sin\theta)(1 - sin\theta)} \nonumber \\
&= \int_{0}^{\alpha} (\frac{1}{1 + sin\theta} + \frac{1}{1 - sin\theta}) \nonumber \\
&= \frac{1}{2} \int_{0}^{\alpha} \frac{dsin\theta}{1+sin\theta} + \frac{1}{2} \int_{0}^{\alpha} \frac{dsin\theta}{1-sin\theta} \nonumber \\
&= \frac{1}{2}ln(1 + sin\alpha) - \frac{1}{2}ln(1 - sin\alpha) \nonumber \\
&= \frac{1}{2}ln(\frac{1 + sin\alpha}{1 - sin\alpha}) \nonumber
\end{align}

到了这步就不用再算了，计算机已经足以胜任。

最终的时间就是：

\frac{1}{2kv_{0}}ln(\frac{1 + sin\alpha}{1 - sin\alpha})

当α=π/2或k和v0中有一个为0时，是永远无法逃脱的。

还要注意要最先判断alpha是否为0，如果一开始就在逃脱点，如果k和v0中有一个为0分母就为0了。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 10010;
const double PI = acos(-1.0);
const double eps = 1e-8;

inline int dblcmp(const double &x)
{
    if(fabs(x) < eps)
    {
        return 0;
    }
    return x > 0 ? 1 : -1;
}

struct Point
{
    double x, y, z;
    inline void input()
    {
        double latitude, longitude;
        scanf("%lf%lf", &latitude, &longitude);
        double theta = (latitude + 90.0) * PI / 180.0;
        double phi = longitude * PI / 180.0;
        x = sin(theta) * cos(phi);
        y = sin(theta) * sin(phi);
        z = cos(theta);
    }
}alien[MAXN], general;
int n, m;
double r, k, v0;

inline Point operator - (const Point &a, const Point &b)
{
    Point c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    c.z = a.z - b.z;
    return c;
}

inline double operator * (const Point &a, const Point &b)
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

inline double pow2(const double &x)
{
    return x * x;
}

struct Vector
{
    Point u, v;
    inline double length() const
    {
        return sqrt(pow2(u.x - v.x) + pow2(u.y - v.y) + pow2(u.z - v.z));
    }
};

inline double operator * (const Vector &a, const Vector &b)
{
    return (a.v - a.u) * (b.v - b.u);
}

inline double getAngle(const Vector &a, const Vector &b)
{
    return acos(fabs(a * b) / a.length() / b.length());
}

int main()
{
    int a, b;
    Vector v1, v2;
    v2.u.x = 0.0;
    v2.u.y = 0.0;
    v2.u.z = 0.0;
    double alpha;
    while(~scanf("%d%d%lf", &n, &m, &r))
    {
        for(int i=0;i<n;++i)
        {
            alien[i].input();
        }
        while(m--)
        {
            scanf("%d%d", &a, &b);
            general.input();
            scanf("%lf%lf", &k, &v0);
            v1.u = alien[a];
            v1.v = alien[b];
            v2.v = general;
            alpha = getAngle(v1, v2);
            if(dblcmp(alpha) == 0)
            {
                printf("0.000\n");
            }
            else if(dblcmp(k) == 0 || dblcmp(v0) == 0 || dblcmp(alpha - PI * 0.5) == 0)
            {
                printf("God Bless Him!\n");
            }
            else
            {
                double ans = log((1 + sin(alpha)) / (1 - sin(alpha))) / k / v0 * 0.5;
                printf("%.3lf\n", fabs(ans));
            }
        }
        printf("\n");
    }
    return 0;
}