F. Isoball: 2D Version

题意：给定一个圆和一个矩阵还有圆行走的方向，问圆往这个方向是否能让整个圆都在矩阵内

分析：先判断圆是否能在矩阵里，再看圆心运动轨迹是否与小矩阵有焦点（只要圆心在小矩阵就一定在矩阵里）

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef long double ld;
void sol(){
        ld x, y, r, vx, vy; // 圆的初始位置 半径 速度向量
        ld lx, ly, rx, ry, llx, lly, rrx, rry; // 矩形位置
        cin >> x >> y >> r >> vx >> vy >> lx >> ly >> rx >> ry;
        llx = lx + r, lly = ly + r, rrx = rx - r, rry = ry - r;
        if (abs(rx-lx)<2*r || abs(ry-ly)<2*r) {//判断圆能否被矩形完全包围
            cout << "No" << endl;
            return; 
        }
        if (vx == 0) { // 当圆沿着y轴方向能否直接进入矩形
            if (llx <= x && x <= rrx) {//x轴位置是否符合
                if ((vy < 0 && y >= lly) || (vy >= 0 && y <= rry)) {//往下并且圆在上面或者往上并且圆在下面 
                    cout << "Yes" << endl;
                    return;
                }
            }
            cout << "No" << endl;
            return;
        }
        if (vy == 0) {//当圆沿着x轴方向能否直接进入矩形
            if (lly <= y && y <= rry ) {
                if ((vx < 0 && x >= llx) || (vx >= 0 && x <= rrx)) {
                    cout << "Yes" << endl;
                    return;
                }
            }
            cout << "No" << endl;
            return;
        }
        pair<ld, ld> o1, o2, o3, o4;
        // 圆心与四条边相交的位置，o1o3为与两边相交可能位置
        // Δy/Δx=vx/vy Y=y+Δy :Y=y+(Δx*vy)/vx X=x+Δx :X=x+(Δy*vx)/vy
        o1.x = llx, o1.y = vy * (o1.x - x) / vx + y;//x=llx
        o3.x = rrx, o3.y = vy * (o3.x - x) / vx + y; //x==rry
        o2.y = rry, o2.x = vx * (o2.y - y) / vy + x;//y==rry
        o4.y = lly, o4.x = vx * (o4.y - y) / vy + x;//y==lly
        //  cout<<o1.x<<" "<<o1.y<<"\n"<<o2.x<<" "<<o2.y<<"\n"<<o3.x<<" "<<o3.y<<"\n"<<o4.x<<" "<<o4.y<<"\n";
        // 从圆心出发的射线能否与矩形四条边相交，检查oi是否会与矩形边相交
        bool s1 = 1, s2 = 1, s3 = 1, s4 = 1;
        if (vx > 0) {//方向 
            if (o1.x < x)
                s1 = 0;
            if (o2.x < x)
                s2 = 0;
            if (o3.x < x)
                s3 = 0;
            if (o4.x < x)
                s4 = 0;
        } else {
            if (o1.x > x)
                s1 = 0;
            if (o2.x > x)
                s2 = 0;
            if (o3.x > x)
                s3 = 0;
            if (o4.x > x)
                s4 = 0;
        }
        if (vy > 0) {
            if (o1.y < y)
                s1 = 0;
            if (o2.y < y)
                s2 = 0;
            if (o3.y < y)
                s3 = 0;
            if (o4.y < y)
                s4 = 0;
        } else {
            if (o1.y > y)
                s1 = 0;
            if (o2.y > y)
                s2 = 0;
            if (o3.y > y)
                s3 = 0;
            if (o4.y > y)
                s4 = 0;
        }
        if (o1.y < lly || o1.y > rry)//在有效区间内 
            s1 = 0;
        if (o2.x < llx || o2.x > rrx)
            s2 = 0;
        if (o3.y < lly || o3.y > rry)
            s3 = 0;
        if (o4.x < llx || o4.x > rrx)
            s4 = 0;
        // 若有一个点与矩形相交，说明在矩形内部
        if (s1 || s2 || s3 || s4) {
            cout << "Yes" << endl;
            return;
        }
        cout << "No" << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--)sol();
    return 0;
}
​