ACM模版

描述


题解

当时做这个题没有完全看清楚题，strictly，严格的，严格处于捕鼠器中，所以只出现在边上是不对的。

这里我们可以在线处理，一边读入，一边缩小时间区间，最后输出时间左区间即可，也就是最少时间，如果中间就能判断输出-1，那就输出-1结束吧。

这里我们需要注意一个问题，既然严格在捕鼠器内，那么最后的时间区间一定是刚好有鼠在边界上的，那么我们为什么输出左区间就可以了呢？这是因为这个题是存在误差判断的题，最早的关闭时间一定是无限接近于左区间的，所以我们只要输出左区间就可以保证在误差范围内，而这里需要注意的是，如果左右区间相等，那么一定是-1，想想为什么，前边输出左区间是因为我们可以保证左右区间中一定存在一个无限接近于左区间的时刻来保证严格处于捕鼠器内，而当左右区间值一样时，就一定不存在，所以 GG~~~

当然，如果左右区间的差超出了数据类型所能表示的位数，而导致两者相等，那就有趣了，这个题就是高精度问题了，然而出题人良心啊，并没有难为我们，大概这种判断误差的问题都不会出现这种坑爹的数据吧。

代码

#include <iostream>

using namespace std;

int n;
double mtx, mty, mtx_, mty_;
double mx, my, mvx, mvy;

double minT = 0, maxT = 1e5 + 10;

int flag = 0;

void getT(double mx, double mvx, double mtx, double mtx_)
{
    if (mvx == 0)
    {
        if (mtx < mx && mx < mtx_)
        {
            return ;
        }
        else
        {
            flag = 1;
            return ;
        }
    }
    else if (mvx < 0)
    {
        if (mx <= mtx)
        {
            flag = 1;
            return ;
        }
        mx = -mx, mvx = -mvx;
        mtx = -mtx, mtx_ = -mtx_;
        swap(mtx, mtx_);
    }
    else
    {
        if (mx >= mtx_)
        {
            flag = 1;
            return ;
        }
    }

    maxT = min(maxT, (mtx_ - mx) / mvx);
    if (mx <= mtx)
    {
        minT = max(minT, (mtx - mx) / mvx);
    }
}

int main()
{
    cin >> n;
    cin >> mtx >> mty >> mtx_ >> mty_;

    for (int i = 0; i < n; i++)
    {
        cin >> mx >> my >> mvx >> mvy;
        getT(mx, mvx, mtx, mtx_);
        if (flag || maxT <= minT)
        {
            cout << "-1\n";
            return 0;
        }
        getT(my, mvy, mty, mty_);
        if (flag || maxT <= minT)
        {
            cout << "-1\n";
            return 0;
        }
    }

    if (maxT > minT)
    {
        cout << minT << endl;
    }
    else
    {
        cout << -1 << endl;
    }

    return 0;
}