QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359050#6426. Interested in Skiinglmf_upWA 6ms3988kbC++208.7kb2024-03-20 11:31:352024-03-20 11:31:36

Judging History

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

  • [2024-03-20 11:31:36]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3988kb
  • [2024-03-20 11:31:35]
  • 提交

answer

#include<bits/stdc++.h>

#define cp const point &
#define cl const line &
#define cc const circle &
#define LD  long double
std::mt19937 rnd(1234567312);
const LD eps = 1e-8;
const LD pi = acosl(-1);
const LD INF = 1e9;
const int mod1 = 998244353, mod2 = 1e9 + 7;

int sgn(LD x)
{
    return x > eps ? 1 : (x < -eps ? -1 : 0);
}

LD sqr(LD x)
{ return x * x; }

long long sqrll(long long x)
{
    return x * x;
}

struct point
{
    LD x, y;

    point()
    {}

    point(LD xx, LD yy)
    { x = xx, y = yy; }

    point operator+(cp a) const
    { return {x + a.x, y + a.y}; }

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

    point operator*(LD t) const
    { return {x * t, y * t}; }

    point operator/(LD t) const
    { return {x / t, y / t}; }

    point rot(LD t) const
    { return {(LD) (x * cosl(t) - y * sinl(t)), (LD) (x * sinl(t) + y * cosl(t))}; }

    point rot90() const
    { return {-y, x}; }

    point rot270() const
    { return point(y, -x); }

    LD len2() const
    { return x * x + y * y; }

    LD len() const
    { return sqrtl(x * x + y * y); }

    point unit() const
    {
        LD d = len();
        return {(LD) (x / d), (LD) (y / d)};
    }

    int on_up()//b不判(0,0)
    {
        return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) < 0);
    }

    void print()
    {
        std::cout << x << ' ' << y << std::endl;
    }

    void read()
    {
        int xx, yy;
        std::cin >> xx >> yy;
        x = xx, y = yy;
    }

    friend bool operator<(cp a, cp b)
    {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }

    friend bool operator>(cp a, cp b)
    {
        return a.x == b.x ? a.y > b.y : a.x > b.x;
    }
};

LD dot(cp a, cp b);

bool operator==(cp a, cp b)
{
//    return !sgn(dot(a - b, a - b));
    return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0; //看题目有无给出确定两实数相等的eps
}

LD dis(cp a, cp b)//两点距离
{
    return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}

LD dot(cp a, cp b)//点乘
{
    return a.x * b.x + a.y * b.y;
}

LD det(cp a, cp b)//叉乘
{
    return a.x * b.y - b.x * a.y;
}

LD deg(point a, point b)
{
    a = a.unit(), b = b.unit();
    LD d = dis(a, b);
    return 2 * asinl(d / 2);
}

bool turn_left_strict(cp a, cp b, cp c)
{
    return sgn(det(b - a, c - a)) > 0;
}

bool turn_left(cp a, cp b, cp c)
{
    return sgn(det(b - a, c - a)) >= 0;
}

struct line
{
    point s, t;

    line()
    {}

    line(point a, point b) : s(a), t(b)
    {}

    void read()
    {
        s.read(), t.read();
    }

    void print()
    {
        s.print(), std::cout << ' ', t.print();
    }

};

struct circle
{
    point c;
    LD r;

    circle()
    {}

    circle(point C, LD R)
    { c = C, r = R; }
};

bool in_circle(cp a, cc b)
{
    return sgn((b.c - a).len() - b.r) <= 0;
}

circle make_circle(point u, point v)
{
    point p = (u + v) / 2;
    return circle(p, (u - p).len());
}

circle make_circle(cp a, cp b, cp c)
{
    point p = b - a, q = c - a;
    point s(dot(p, p) / 2, dot(q, q) / 2);
    LD d = det(p, q);
    p = point(det(s, point(p.y, q.y)), det(point(p.x, q.x), s)) / d;
    return circle(a + p, p.len());
}

circle min_circle(std::vector<point> p)
{
    circle ret(p[0], 0);
    std::shuffle(p.begin(), p.end(), rnd);
    int len = p.size();
    for (int i = 0; i < len; i++)
        if (!in_circle(p[i], ret))
        {
            ret = circle(p[i], 0);
            for (int j = 0; j < i; j++)
                if (!in_circle(p[j], ret))
                {
                    ret = make_circle(p[j], p[i]);
                    for (int k = 0; k < j; ++k)
                        if (!in_circle(p[k], ret))
                            ret = make_circle(p[i], p[j], p[k]);
                }
        }
    return ret;
}

LD get_rad(point a, point b)
{
    if (a == point(0, 0) || b == point(0, 0))
        return 0;
    else
    {
        return acosl(dot(a, b) / (a.len() * b.len()));
    }
}

bool same_dir(cl a, cl b)//判断方向是否一致
{
    return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}

bool point_on_line(cp a, cl l)//判断点是否在直线上
{
    return sgn(det(a - l.s, l.t - l.s)) == 0;
}

bool point_on_segment(cp a, cl l)//判断点是否在线段上
{
    return point_on_line(a, l) && sgn(dot(l.s - a, l.t - a)) < 0;//(<=代表可以端点
}

bool two_side(cp a, cp b, cl c)//判断两个点是否在线段的两边
{
    return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}

bool intersect_judge_strict(cl a, cl b)
{
    return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}

bool intersect_judge(cl a, cl b)
{//判断两个线段是否相交
    if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) ||
        point_on_segment(b.t, a))
        return true;
    return intersect_judge_strict(a, b);
}


point line_intersect(cl a, cl b)
{//得到两线段的交点
    LD s1 = det(a.t - a.s, b.s - a.s);
    LD s2 = det(a.t - a.s, b.t - a.s);
    return (b.s * s2 - b.t * s1) / (s2 - s1);
}

LD point_to_segment(cp a, cl b)
{//点到线段的距离
    if (b.s == b.t)
        return dis(a, b.s);
    if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
        return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
    return std::min(dis(a, b.s), dis(a, b.t));

}

std::vector<point> circle_intersect(cc a, cc b)//求两个圆的交
{
    if (a.c == b.c || sgn(dis(a.c, b.c) - a.r - b.r) > 0 || sgn(dis(a.c, b.c) - abs(a.r - b.r)) < 0)
        return {};
    point r = (b.c - a.c).unit();
    LD d = dis(a.c, b.c);
    LD x = ((sqr(a.r) - sqr(b.r)) / d + d) / 2;
    LD h = sqrtl(sqr(a.r) - sqr(x));
    if (sgn(h) == 0)return {a.c + r * x};
    return {a.c + r * x + r.rot90() * h, a.c + r * x - r.rot90() * h};
}

std::vector<point> tangent(cp a, cc b)//求一个点关于圆的切线
{
    circle p = make_circle(a, b.c);
    return circle_intersect(p, b);
}


std::vector<point> convex_hull(std::vector<point> a)
{//凸包,字典序
    int n = (int) a.size(), cnt = 0;
    if (n < 2) return a;
    std::sort(a.begin(), a.end()); // less<pair>
    std::vector<point> ret;
    for (int i = 0; i < n; ++i)
    {
        while (cnt > 1
               && !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
            --cnt, ret.pop_back();
        ++cnt, ret.push_back(a[i]);
    }
    int fixed = cnt;
    for (int i = n - 2; i >= 0; --i)
    {
        while (cnt > fixed
               && !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
            --cnt, ret.pop_back();
        ++cnt, ret.push_back(a[i]);
    }
    ret.pop_back();
    return ret;
}

void solve()
{
    int n, m, vy;
    std::cin >> n >> m >> vy;
    std::vector<point> pu;
    std::vector<line> li(n);
    for (int i = 0; i < n; i++)
    {
        point p1, p2;
        p1.read(), p2.read();
        pu.push_back(p1);
        pu.push_back(p2);
        li[i] = line(p1, p2);
    }
    std::sort(pu.begin(), pu.end(), [&](auto u, auto v)
    { return u.y < v.y; });
    int len_pu = pu.size();
    std::vector<LD> dp(len_pu, 1e18);
    std::function<bool(line)> check = [&](line a)
    {
        for (int i = 0; i < n; i++)
        {
            if (intersect_judge_strict(a, li[i]))
                return false;
        }
        return true;
    };
    LD ans = 1e18;
    for (int i = 0; i < len_pu; i++)
    {
        auto [x, y] = pu[i];
        if (sgn(x - m) == 0 || sgn(x + m) == 0)
            continue;
        if (check(line(point(x, -11111), pu[i])))
        {
            dp[i] = 0;
            if (check(line(point(x, 11111), pu[i])))
            {
                std::cout << 0 << std::endl;
                return;
            }
        }
        for (int j = 0; j < i; j++)
        {
            if (sgn(pu[j].y - pu[i].y) == 0)
                break;
            if (check(line(pu[i], pu[j])))
                dp[i] = std::min(dp[i], std::max(dp[j], std::abs(pu[j].x - pu[i].x) / ((pu[i].y - pu[j].y)) ));
        }
        if (check(line(point(x, 11111), pu[i])))
            ans = std::min(ans, dp[i]);
    }
    if (ans > 1e9)
    {
        std::cout << -1 << std::endl;
        return;
    }
    if (check(line(point(0, -11111), point(0, 11111))))
        ans = 0;
    std::cout << ans*vy << std::endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
    std::cout << std::fixed << std::setprecision(10);
    int T = 1;
    for (int i = 1; i <= T; i++)
        solve();
}
/*


 */

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3932kb

input:

3 2 1
-2 0 1 0
-1 4 2 4
0 1 0 3

output:

1.0000000000

result:

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

Test #2:

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

input:

2 1 2
-1 0 1 0
1 1 0 1

output:

-1

result:

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

Test #3:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

2 3 7
-3 0 2 2
3 1 -2 17

output:

1.8666666667

result:

ok found '1.8666667', expected '1.8666667', error '0.0000000'

Test #4:

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

input:

1 100 1
-100 0 99 0

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

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

input:

3 8 3
-8 -9 0 -9
-6 -6 6 6
8 9 0 9

output:

6.0000000000

result:

ok found '6.0000000', expected '6.0000000', error '0.0000000'

Test #6:

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

input:

3 8 3
-8 9 0 9
-6 6 6 -6
8 -9 0 -9

output:

6.0000000000

result:

ok found '6.0000000', expected '6.0000000', error '0.0000000'

Test #7:

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

input:

2 1 2
-1 0 0 0
1 1 0 1

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

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

input:

3 9 10
-9 -26 0 -8
-6 -6 6 6
9 26 0 8

output:

30.0000000000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #9:

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

input:

3 9 10
-9 26 0 8
-6 6 6 -6
9 -26 0 -8

output:

30.0000000000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #10:

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

input:

4 9 5
-9 -4 -3 0
-6 2 6 2
-6 -6 2 -8
-4 -12 9 -25

output:

7.5000000000

result:

ok found '7.5000000', expected '7.5000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3988kb

input:

100 10000 2
1663 -5179 1091 -542
-5687 -1048 7838 4346
3959 -2780 1099 -9402
-8661 -856 3945 7651
-1688 5290 -3518 2625
10000 -8028 5857 -9678
-9929 4601 -6350 3819
-1173 -9608 -2422 -9939
10000 -4668 5423 -2597
-572 -9335 -5787 -7658
-10000 1589 3117 9331
9818 4874 1345 1669
9026 -8243 2952 -6411
8...

output:

5.9776075427

result:

ok found '5.9776075', expected '5.9776075', error '0.0000000'

Test #12:

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

input:

20 100 5
100 55 77 -18
60 -33 45 -1
41 41 -84 53
66 -77 30 -70
44 -15 -45 -98
-36 19 67 29
51 -71 89 -50
100 -48 92 -39
43 20 -22 -33
10 -71 7 -52
-100 -9 -4 13
-100 90 -19 81
73 67 6 54
-86 2 -91 67
59 -35 77 -55
-43 -40 -58 -41
100 82 -39 55
40 -17 39 -12
42 4 84 -52
61 78 -46 86

output:

27.0000000000

result:

ok found '27.0000000', expected '27.0000000', error '0.0000000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

20 100 1
90 -37 -90 90
-61 46 -83 42
26 -45 -89 -79
-100 -3 -51 -34
40 -57 22 -70
90 55 17 75
5 -50 -35 24
-1 -20 33 -19
-69 78 100 -13
-45 -52 -89 -15
100 -100 -3 -23
49 84 78 95
-48 43 -21 -23
100 53 78 84
65 -42 84 -61
100 23 100 19
-58 38 -48 18
26 -53 -51 -92
29 37 -81 90
-5 82 43 30

output:

1.3181818182

result:

ok found '1.3181818', expected '1.3181818', error '0.0000000'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3884kb

input:

100 10000 9
9893 -5 -4023 94
2920 -32 -2174 -97
7462 24 4169 40
-6157 -25 -6492 40
5908 -16 647 48
4128 -19 -5163 -5
4082 96 7645 37
-8896 29 -2485 59
165 1 -1634 59
7644 -64 6345 -96
-8569 46 -5850 72
-2219 -64 -5429 -13
641 -36 -3923 -25
-1947 6 -3957 43
8241 -6 -2456 77
5268 -95 890 -75
3296 78 -...

output:

3037.1538461538

result:

ok found '3037.1538462', expected '3037.1538462', error '0.0000000'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

10 50 4
5 -45 22 -48
-50 20 -23 19
-43 -29 35 31
50 -33 40 48
-49 -32 0 -33
16 -50 21 -49
50 -38 -22 -18
-49 50 11 14
20 -23 16 -11
-27 -15 35 32

output:

3.3548387097

result:

ok found '3.3548387', expected '3.3548387', error '0.0000000'

Test #16:

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

input:

10 50 1
-50 -3 28 -3
7 -30 2 -30
34 39 50 39
16 22 43 22
50 -32 7 -32
50 15 -2 15
-15 -42 24 -42
14 -26 28 -26
23 -10 -39 -10
50 -44 -31 -44

output:

1.6666666667

result:

ok found '1.6666667', expected '1.6666667', error '0.0000000'

Test #17:

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

input:

10 50 2
35 10 7 22
-47 -23 -34 8
44 27 14 47
50 -13 -43 -48
44 -15 20 -12
-42 -34 11 -5
50 -5 -32 19
17 -39 46 -27
50 -2 11 20
-1 29 30 31

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #18:

score: 0
Accepted
time: 6ms
memory: 3932kb

input:

100 10000 10
0 9993 -10000 9997
-8432 1663 -4444 1091
-6362 3959 -103 1099
-6051 -8548 -5705 -3821
-1799 4343 -9251 8281
-10000 -1137 -6247 718
-10000 -1352 -641 -1609
-2741 -1688 -2924 -3518
-10000 5035 -7198 5857
-4181 -9929 -3009 -6350
-9568 -9578 -7653 -9810
-9208 2799 -8703 3189
-10000 -3228 -3...

output:

0.0015005252

result:

ok found '0.0015005', expected '0.0015005', error '0.0000000'

Test #19:

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

input:

7 70 6
-63 -598 7 -598
70 260 14 104
35 26 -21 -182
-21 -286 -21 -494
-56 -208 -56 -572
-70 0 0 0
-42 -208 -14 -208

output:

1.6153846154

result:

ok found '1.6153846', expected '1.6153846', error '0.0000000'

Test #20:

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

input:

1 10 1
-10 0 -10 10

output:

-1

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '-1.0000000', error = '1.0000000'