AIZU OJ 2308 基础计算几何学习

传送门：AOJ 2308、

题意：平面上有n个障碍物，给出障碍物的左下角和右上角（矩形），现在要从原点以初速度V向任意角度发射一只鸟，射出的鸟将呈抛物线飞出，直到撞到障碍物为止，鸟在飞行的过程中可以下一个蛋，蛋将竖直下落，直到撞到障碍物为止，问能不能击中（X,Y）位置的猪。

思路：大白例题，主要体现的是计算几何解题过程中用到的极限转化思想，我们枚举角度时只需要枚举经过障碍物的左上角或者右上角的曲线就行了，任意解都能通过慢慢减小初射角度转化成这种极限情况的解。

像这样在几何问题中，当可行解可以取一段连续的值时，很多时候只要考虑边界的极限情况就能够顺利解决问题了。

代码：

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
const double g = 9.8;
const int MAXN = 55;
double L[MAXN],R[MAXN],B[MAXN],T[MAXN];
double N,V,X,Y;
// 计算以Vy的速度竖直向上射出t秒后的位置
double calc(double vy, double t)
{
    return vy * t - g * t * t / 2;
}
// a相对于l和r的位置
int cmp(double l, double r, double a)// 注意判断大小的时候的误差处理
{
    if(a < l + eps) return -1;//if(a <= l)
    if(a > r - eps) return 1;//if(a >= r)
    return 0;
}
// 判断当射出路径经过点（qx,qy）时，卵是否能击中猪
//设初速度在x方向和y方向的分量为vx和vy，设通过（qx，qy）的时间为t
//求解联立方程式vx^2 + vy^2 = V^2 , vx * t = qx, vy * t - g * t^2 * 1/2 = qy
bool check(double qx, double qy)
{
    double a = g * g / 4, b = g * qy - V * V, c = qx * qx + qy * qy;
    double D = b * b - 4 * a * c;
    if(D < 0 && D > -eps) D = 0; //误差处理
    if(D < 0) return false;
    for(int d=-1;d<=1;d+=2)
    {
        double t2 = (-b + d * sqrt(D)) / (2 * a);//解出来的是t^2
        if(t2 <= 0) continue;
        double t = sqrt(t2);
        double vx = qx / t,vy = (qy + g * t * t / 2) / t;
        //判断是否通过猪的正上方
        double yt = calc(vy, X / vx);
        if(yt < Y - eps) continue; //yt < Y
        bool flag = 1;
        for(int i=0;i<N;i++)
        {
            if(L[i] >= X) continue;
            //判断在猪正上方的鸟和猪之间是否有障碍物
            if(R[i] == X && Y <= T[i] && B[i] <= yt)// 由于预处理，这里已经保证了L[i] <= X <= R[i]
            flag = false;
            //判断在飞到猪正上方之前是否会撞到障碍物
            int yl = cmp(B[i], T[i], calc(vy, L[i] / vx));//在障碍物左边缘时的相对位置
            int yr = cmp(B[i], T[i], calc(vy, R[i] / vx));//在障碍物右边缘时的相对位置
            int xh = cmp(L[i], R[i], vx * vy / g);//最高点的相对位置
            int yh = cmp(B[i], T[i], calc(vy, vy / g));
            if(xh == 0 && yh >= 0 && yl < 0) flag = false;
            if(yl * yr <= 0) flag = false;
        }
        if(flag) return 1;
    }
    return 0;
}
int main()
{
    cin >> N >> V >> X >> Y;
    for(int i=0;i<N;i++)
    cin >> L[i] >> B[i] >> R[i] >> T[i], R[i] = min(R[i], X);//预处理，截掉猪以右的障碍物
    bool flag = check(X, Y);//直接撞上猪的情况
    for(int i=0;i<N;i++)
    {
        flag |= check(L[i], T[i]);//经过障碍物左上角的情况
        flag |= check(R[i], T[i]);//经过障碍物右上角的情况
    }
    puts(flag ? "Yes" : "No");
    return 0;
}