QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#818274#9663. Reverse Pairs ColoringccsurzwWA 0ms3716kbC++234.5kb2024-12-17 18:10:552024-12-17 18:11:00

Judging History

This is the latest submission verdict.

  • [2024-12-17 18:11:00]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3716kb
  • [2024-12-17 18:10:55]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define double ld
#define N 201000
#define endl '\n'
ll mod = 998244353;
ld x, y, r, Vx, Vy,nx,ny;
ld Lx, Ly, Rx, Ry;
ld k, b;
ld get_y(ld x) {
    return k * x + b;
}
ld get_x(ld y) {
    return (y - b) / k;
}
struct Point {
    ld x;
    ld y;
};
bool isOnRay(Point p, Point rayStart, Point rayDirection) {
    Point vecToPoint = { p.x - rayStart.x, p.y - rayStart.y };

    double crossProduct = vecToPoint.x * rayDirection.y - vecToPoint.y * rayDirection.x;
    const double eps = 1e-9;  
    if (std::fabs(crossProduct) > eps) {
        return false;
    }

    // 计算点乘判断方向,若点乘大于等于0,表示点在射线的延伸方向上(相对于起点)
    double dotProduct = vecToPoint.x * rayDirection.x + vecToPoint.y * rayDirection.y;
    return dotProduct >= 0;
}
void solve() {
    cin >> x >> y >> r >> Vx >> Vy;
    cin >> Lx >> Ly >> Rx >> Ry;
    if (Vx == 0)
    {
        if (Vy < 0)
        {
            if (y - r >= Ly)
            {
                if (Lx <= x - r && x - r <= Rx)
                {
                    if (Lx <= x + r && x + r <= Rx)
                    {
                        if (Ry - Ly >= 2 * r)
                        {
                            cout << "Yes" << endl;
                            return;
                        }
                    }
                }
            }
        }
        else
        {
            if (y + r <= Ry)
            {
                if (Lx <= x - r && x - r <= Rx)
                {
                    if (Lx <= x + r && x + r <= Rx)
                    {
                        if (Ry - Ly >= 2 * r)
                        {
                            cout << "Yes" << endl;
                            return;
                        }
                    }
                }
            }
        }
        cout << "No" << endl;
        return;
    }

    if (Vy == 0)
    {
        if (Vx > 0)
        {
            if (x + r <= Rx)
            {
                if (Ly <= y - r && y - r <= Ry)
                {
                    if (Ly <= y + r && y + r <= Ry)
                    {
                        if (Rx - Lx >= 2 * r)
                        {
                            cout << "Yes" << endl;
                            return;
                        }
                    }
                }
            }
        }
        else
        {
            if (x - r >= Lx)
            {
                if (Ly <= y - r && y - r <= Ry)
                {
                    if (Ly <= y + r && y + r <= Ry)
                    {
                        if (Rx - Lx >= 2 * r)
                        {
                            cout << "Yes" << endl;
                            return;
                        }
                    }
                }
            }
        }
        cout << "No" << endl;
        return;
    }
    Point p, start, ray;
    start.x = x;
    start.y = y;
    ray.x = Vx;
    ray.y = Vy;
    k = Vy / Vx;//移动方向方程的k
    b = y - k * x;//b
    
    //将矩形左边的顶点加r
    nx = Lx + r;//新的圆坐标
    ny = get_y(nx);//新的圆坐标
    p.x = nx;
    p.y = ny;
    if (ny - Ly >= r && Ry - ny >= r && Rx - nx >= r) {
        if (isOnRay(p ,start,ray )) {//判断是移动方向是否正确
            cout << "Yes" << endl;
            return;
        }
    }
    
    nx = Rx - r;//新的圆坐标
    ny = get_y(nx);//新的圆坐标
    p.x = nx;
    p.y = ny;
    if (ny - Ly >= r && Ry - ny >= r && nx - Lx >= r) {
        if (isOnRay(p, start, ray)) {//判断是移动方向是否正确
            cout << "Yes" << endl;
            return;
        }
    }

    ny = Ly + r;
    nx = get_x(ny);
    p.x = nx;
    p.y = ny;
    if (nx - Lx >= r && Ry - ny >= r && Rx - nx >= r) {
        if (isOnRay(p, start, ray)) {//判断是移动方向是否正确
            cout << "Yes" << endl;
            return;
        }
    }

    ny = Ry - r;
    nx = get_x(ny);
    p.x = nx;
    p.y = ny;
    if (nx - Lx >= r && ny - Ly >= r && Rx - nx >= r) {
        if (isOnRay(p, start, ray)) {//判断是移动方向是否正确
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3716kb

input:

9
5 9 1 8 2 6 4 7 3

output:

No
No
No
No
No
No
No
No
No

result:

wrong answer 1st lines differ - expected: '5', found: 'No'