QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735287#9576. Ordainer of Inexorable JudgmentBDDLWA 0ms4372kbC++233.6kb2024-11-11 18:57:562024-11-11 18:57:58

Judging History

你现在查看的是最新测评结果

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-11-14 21:58:28]
  • hack成功,自动添加数据
  • (/hack/1181)
  • [2024-11-11 18:57:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4372kb
  • [2024-11-11 18:57:56]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const double PI = acos(-1);
const double eps = 1e-12;
struct point
{
    double x, y;
};

int cmp(double a, double b)
{
    if(fabs(a - b) < eps)
        return 0;
    if(a < b)
        return -1;
    return 1;
}

int sign(double a)
{
    if(fabs(a) < eps)
        return 0;
    if(a < 0)
        return -1;
    return 1;
}

point operator- (point a, point b)
{
    return {a.x - b.x, a.y - b.y};
}

point operator/ (point a, double b)
{
    return {a.x / b, a.y / b};
}

double operator* (point a, point b)
{
    return a.x * b.x + a.y * b.y;
}

point operator* (point a, double b)
{
    return {a.x * b, a.y * b};
}

point rotate(point a, double b)
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

double cross(point a, point b)
{
    return a.x * b.y - a.y * b.x;
}

double get_dist(point a, point b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

void solve()
{
    point O = {0, 0};
    double n, d, t;
    point v0, v1;
    cin >> n >> v1.x >> v1.y >> d >> t;
    v0 = v1;
    vector<point> a(n + 1);
    bool dot = 0, flag1 = 0, flag2 = 0;
    for(int i = 1; i <= n; i ++)
    {
        int x, y; 
        cin >> x >> y;
        a[i] = (point){x, y};
        point p1 = rotate(v0, -PI / 2), p2 = rotate(v0, PI / 2);
        if(sign(cross(v0, a[i] - p1)) < 0)
            flag1 = true;
        if(sign(cross(v0, a[i] - p2)) > 0)
            flag2 = true;
        if(sign(v0 * a[i]) > 0)
            dot = true;
    }
    if(flag1 && flag2 && dot)
        v0 = rotate(v0, PI);
    
    double l, r;
    l = atan2(v0.y, v0.x);
    if(l < 0)
        l += PI * 2;
    r = l + PI * 2;
    point vl = v0;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        point v = rotate(vl, l - mid);
        point p = rotate(v, -PI / 2) / get_dist(O, v) * d;
        bool flag = false;
        for(int i = 1; i <= n; i ++)
        {
            if(sign(cross(v, a[i] - p)) < 0)
                flag = true;
        }
        if(flag)
            r = mid;
        else
        {
            l = mid;
            vl = v;
        }
    }
    double st_angle = l;

    l = atan2(v0.y, v0.x);
    if(l < 0)
        l += PI * 2;
    r = l + PI * 2;
    vl = v0;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        // cerr << mid << endl;
        point v = rotate(vl, l - mid);
        point p = rotate(v, PI / 2) / get_dist(O, v) * d;
        // cerr << p.x << ' ' << p.y << endl;
        bool flag = false;
        int num = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(sign(cross(v, a[i] - p)) > 0)
                flag = true;
        }
        if(flag)
        {
            l = mid;
            vl = v;
        }
        else
            r = mid;
    }
    double ed_angle = l;
    
    if(st_angle - PI * 2 >= 0 && ed_angle - PI * 2 >= 0)
    {
        st_angle -= PI * 2;
        ed_angle -= PI * 2;
    }
    // printf("%.8lf\n", st_angle);
    // printf("%.8lf\n", ed_angle);

    int cnt = t / (PI * 2);
    t -= cnt * PI * 2;
    // cerr << cnt << ' ' << t << endl;

    double v0_angle = atan2(v1.y, v1.x);
    if(v0_angle < 0)
        v0_angle += PI * 2;
    double v1_angle = v0_angle + t;
    // cerr << v0_angle << ' ' << v1_angle << endl;
    
    double ans = max(0.0, min(ed_angle, v1_angle) - max(st_angle, v0_angle)) + cnt * (ed_angle - st_angle);
    printf("%.7lf\n", ans);
}
signed main()
{
    int T = 1;
    while (T --) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4188kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.0000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4216kb

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.5707963

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4172kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.7077523

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4320kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.3842413

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4372kb

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

2500.2406700

result:

ok found '2500.2406700', expected '2500.2406700', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4260kb

input:

4 1 0 1 10000
-2 3400
-4 10000
-4 -10000
-2 -3400

output:

4999.2191154

result:

ok found '4999.2191154', expected '4999.2191154', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4164kb

input:

4 1 0 1 10000
-2 3300
-4 10000
-4 -10000
-2 -3300

output:

4999.2003919

result:

ok found '4999.2003919', expected '4999.2003919', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4344kb

input:

4 -3040 2716 2147 2
-9033 -8520
-8999 -8533
-8988 -8511
-9004 -8495

output:

0.3508301

result:

ok found '0.3508301', expected '0.3508301', error '0.0000000'

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 4372kb

input:

3 8168 -766 1549 1256
-3951 -6425
-3874 -6439
-3911 -6389

output:

84.4086969

result:

wrong answer 1st numbers differ - expected: '84.8328612', found: '84.4086969', error = '0.0050000'