QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185405#5612. Picking Up Steamucup-team004WA 1ms3828kbC++2014.3kb2023-09-22 01:03:432023-09-22 01:03:44

Judging History

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

  • [2023-09-22 01:03:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3828kb
  • [2023-09-22 01:03:43]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
struct Point {
    T x;
    T y;
    Point(const T &x_ = 0, const T &y_ = 0) : x(x_), y(y_) {}
    
    template<class U>
    operator Point<U>() {
        return Point<U>(U(x), U(y));
    }
    Point &operator+=(const Point &p) & {
        x += p.x;
        y += p.y;
        return *this;
    }
    Point &operator-=(const Point &p) & {
        x -= p.x;
        y -= p.y;
        return *this;
    }
    Point &operator*=(const T &v) & {
        x *= v;
        y *= v;
        return *this;
    }
    Point &operator/=(const T &v) & {
        x /= v;
        y /= v;
        return *this;
    }
    Point operator-() const {
        return Point(-x, -y);
    }
    friend Point operator+(Point a, const Point &b) {
        return a += b;
    }
    friend Point operator-(Point a, const Point &b) {
        return a -= b;
    }
    friend Point operator*(Point a, const T &b) {
        return a *= b;
    }
    friend Point operator/(Point a, const T &b) {
        return a /= b;
    }
    friend Point operator*(const T &a, Point b) {
        return b *= a;
    }
    friend bool operator==(const Point &a, const Point &b) {
        return a.x == b.x && a.y == b.y;
    }
    friend std::istream &operator>>(std::istream &is, Point &p) {
        return is >> p.x >> p.y;
    }
    friend std::ostream &operator<<(std::ostream &os, const Point &p) {
        return os << "(" << p.x << ", " << p.y << ")";
    }
};

template<class T>
struct Line {
    Point<T> a;
    Point<T> b;
    Line(const Point<T> &a_ = Point<T>(), const Point<T> &b_ = Point<T>()) : a(a_), b(b_) {}
};

template<class T>
T dot(const Point<T> &a, const Point<T> &b) {
    return a.x * b.x + a.y * b.y;
}

template<class T>
T cross(const Point<T> &a, const Point<T> &b) {
    return a.x * b.y - a.y * b.x;
}

template<class T>
T square(const Point<T> &p) {
    return dot(p, p);
}

template<class T>
double length(const Point<T> &p) {
    return std::sqrt(square(p));
}

template<class T>
double length(const Line<T> &l) {
    return length(l.a - l.b);
}

template<class T>
Point<T> normalize(const Point<T> &p) {
    return p / length(p);
}

template<class T>
bool parallel(const Line<T> &l1, const Line<T> &l2) {
    return cross(l1.b - l1.a, l2.b - l2.a) == 0;
}

template<class T>
double distance(const Point<T> &a, const Point<T> &b) {
    return length(a - b);
}

template<class T>
double distancePL(const Point<T> &p, const Line<T> &l) {
    return std::abs(cross(l.a - l.b, l.a - p)) / length(l);
}

template<class T>
double distancePS(const Point<T> &p, const Line<T> &l) {
    if (dot(p - l.a, l.b - l.a) < 0) {
        return distance(p, l.a);
    }
    if (dot(p - l.b, l.a - l.b) < 0) {
        return distance(p, l.b);
    }
    return distancePL(p, l);
}

template<class T>
Point<T> rotate(const Point<T> &a) {
    return Point(-a.y, a.x);
}

template<class T>
int sgn(const Point<T> &a) {
    return a.y > 0 || (a.y == 0 && a.x > 0) ? 1 : -1;
}

template<class T>
bool pointOnLineLeft(const Point<T> &p, const Line<T> &l) {
    return cross(l.b - l.a, p - l.a) > 0;
}

template<class T>
Point<T> lineIntersection(const Line<T> &l1, const Line<T> &l2) {
    return l1.a + (l1.b - l1.a) * (cross(l2.b - l2.a, l1.a - l2.a) / cross(l2.b - l2.a, l1.a - l1.b));
}

template<class T>
bool pointOnSegment(const Point<T> &p, const Line<T> &l) {
    return cross(p - l.a, l.b - l.a) == 0 && std::min(l.a.x, l.b.x) <= p.x && p.x <= std::max(l.a.x, l.b.x)
        && std::min(l.a.y, l.b.y) <= p.y && p.y <= std::max(l.a.y, l.b.y);
}

template<class T>
bool pointInPolygon(const Point<T> &a, const std::vector<Point<T>> &p) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
        if (pointOnSegment(a, Line(p[i], p[(i + 1) % n]))) {
            return true;
        }
    }
    
    int t = 0;
    for (int i = 0; i < n; i++) {
        auto u = p[i];
        auto v = p[(i + 1) % n];
        if (u.x < a.x && v.x >= a.x && pointOnLineLeft(a, Line(v, u))) {
            t ^= 1;
        }
        if (u.x >= a.x && v.x < a.x && pointOnLineLeft(a, Line(u, v))) {
            t ^= 1;
        }
    }
    
    return t == 1;
}

// 0 : not intersect
// 1 : strictly intersect
// 2 : overlap
// 3 : intersect at endpoint
template<class T>
std::tuple<int, Point<T>, Point<T>> segmentIntersection(const Line<T> &l1, const Line<T> &l2) {
    if (std::max(l1.a.x, l1.b.x) < std::min(l2.a.x, l2.b.x)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (std::min(l1.a.x, l1.b.x) > std::max(l2.a.x, l2.b.x)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (std::max(l1.a.y, l1.b.y) < std::min(l2.a.y, l2.b.y)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (std::min(l1.a.y, l1.b.y) > std::max(l2.a.y, l2.b.y)) {
        return {0, Point<T>(), Point<T>()};
    }
    if (cross(l1.b - l1.a, l2.b - l2.a) == 0) {
        if (cross(l1.b - l1.a, l2.a - l1.a) != 0) {
            return {0, Point<T>(), Point<T>()};
        } else {
            auto maxx1 = std::max(l1.a.x, l1.b.x);
            auto minx1 = std::min(l1.a.x, l1.b.x);
            auto maxy1 = std::max(l1.a.y, l1.b.y);
            auto miny1 = std::min(l1.a.y, l1.b.y);
            auto maxx2 = std::max(l2.a.x, l2.b.x);
            auto minx2 = std::min(l2.a.x, l2.b.x);
            auto maxy2 = std::max(l2.a.y, l2.b.y);
            auto miny2 = std::min(l2.a.y, l2.b.y);
            Point<T> p1(std::max(minx1, minx2), std::max(miny1, miny2));
            Point<T> p2(std::min(maxx1, maxx2), std::min(maxy1, maxy2));
            if (!pointOnSegment(p1, l1)) {
                std::swap(p1.y, p2.y);
            }
            if (p1 == p2) {
                return {3, p1, p2};
            } else {
                return {2, p1, p2};
            }
        }
    }
    auto cp1 = cross(l2.a - l1.a, l2.b - l1.a);
    auto cp2 = cross(l2.a - l1.b, l2.b - l1.b);
    auto cp3 = cross(l1.a - l2.a, l1.b - l2.a);
    auto cp4 = cross(l1.a - l2.b, l1.b - l2.b);
    
    if ((cp1 > 0 && cp2 > 0) || (cp1 < 0 && cp2 < 0) || (cp3 > 0 && cp4 > 0) || (cp3 < 0 && cp4 < 0)) {
        return {0, Point<T>(), Point<T>()};
    }
    
    Point p = lineIntersection(l1, l2);
    if (cp1 != 0 && cp2 != 0 && cp3 != 0 && cp4 != 0) {
        return {1, p, p};
    } else {
        return {3, p, p};
    }
}

template<class T>
double distanceSS(const Line<T> &l1, const Line<T> &l2) {
    if (std::get<0>(segmentIntersection(l1, l2)) != 0) {
        return 0.0;
    }
    return std::min({distancePS(l1.a, l2), distancePS(l1.b, l2), distancePS(l2.a, l1), distancePS(l2.b, l1)});
}

template<class T>
bool segmentInPolygon(const Line<T> &l, const std::vector<Point<T>> &p) {
    int n = p.size();
    if (!pointInPolygon(l.a, p)) {
        return false;
    }
    if (!pointInPolygon(l.b, p)) {
        return false;
    }
    for (int i = 0; i < n; i++) {
        auto u = p[i];
        auto v = p[(i + 1) % n];
        auto w = p[(i + 2) % n];
        auto [t, p1, p2] = segmentIntersection(l, Line(u, v));
        
        if (t == 1) {
            return false;
        }
        if (t == 0) {
            continue;
        }
        if (t == 2) {
            if (pointOnSegment(v, l) && v != l.a && v != l.b) {
                if (cross(v - u, w - v) > 0) {
                    return false;
                }
            }
        } else {
            if (p1 != u && p1 != v) {
                if (pointOnLineLeft(l.a, Line(v, u))
                    || pointOnLineLeft(l.b, Line(v, u))) {
                    return false;
                }
            } else if (p1 == v) {
                if (l.a == v) {
                    if (pointOnLineLeft(u, l)) {
                        if (pointOnLineLeft(w, l)
                            && pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, l)
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    }
                } else if (l.b == v) {
                    if (pointOnLineLeft(u, Line(l.b, l.a))) {
                        if (pointOnLineLeft(w, Line(l.b, l.a))
                            && pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, Line(l.b, l.a))
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    }
                } else {
                    if (pointOnLineLeft(u, l)) {
                        if (pointOnLineLeft(w, Line(l.b, l.a))
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, l)
                            || pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return true;
}

template<class T>
std::vector<Point<T>> hp(std::vector<Line<T>> lines) {
    std::sort(lines.begin(), lines.end(), [&](auto l1, auto l2) {
        auto d1 = l1.b - l1.a;
        auto d2 = l2.b - l2.a;
        
        if (sgn(d1) != sgn(d2)) {
            return sgn(d1) == 1;
        }
        
        return cross(d1, d2) > 0;
    });
    
    std::deque<Line<T>> ls;
    std::deque<Point<T>> ps;
    for (auto l : lines) {
        if (ls.empty()) {
            ls.push_back(l);
            continue;
        }
        
        while (!ps.empty() && !pointOnLineLeft(ps.back(), l)) {
            ps.pop_back();
            ls.pop_back();
        }
        
        while (!ps.empty() && !pointOnLineLeft(ps[0], l)) {
            ps.pop_front();
            ls.pop_front();
        }
        
        if (cross(l.b - l.a, ls.back().b - ls.back().a) == 0) {
            if (dot(l.b - l.a, ls.back().b - ls.back().a) > 0) {
                
                if (!pointOnLineLeft(ls.back().a, l)) {
                    assert(ls.size() == 1);
                    ls[0] = l;
                }
                continue;
            }
            return {};
        }
        
        ps.push_back(lineIntersection(ls.back(), l));
        ls.push_back(l);
    }
    
    while (!ps.empty() && !pointOnLineLeft(ps.back(), ls[0])) {
        ps.pop_back();
        ls.pop_back();
    }
    if (ls.size() <= 2) {
        return {};
    }
    ps.push_back(lineIntersection(ls[0], ls.back()));
    
    return std::vector(ps.begin(), ps.end());
}

using real = long double;
using P = Point<real>;

constexpr real eps = 1E-6;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<P> a(n + 1);
    for (int i = 0; i <= n; i++) {
        int x, y;
        std::cin >> x >> y;
        a[i] = P(x, y);
    }
    
    int x0;
    std::cin >> x0;
    
    P s, vec;
    real r, v;
    std::cin >> s.x >> s.y >> r >> vec.x >> vec.y >> v;
    
    int p = 0;
    while (a[p + 1].x < x0) {
        p++;
    }
    P o = a[p] + (a[p + 1] - a[p]) / (a[p + 1].x - a[p].x) * (x0 - a[p].x);
    P ang;
    vec = normalize(vec) * v;
    real ans = -1;
    
    constexpr real inf = 1E9;
    
    auto work = [&](P u, P v) {
        if (u.x > v.x - eps) {
            return;
        }
        if (s.x > u.x + eps && s.x < v.x - eps && pointOnLineLeft(s, Line(u, v))) {
            ans = 0;
            return;
        }
        Line l1(u, P(u.x, inf)), l2(u, v), l3(v, P(v.x, inf));
        real lo = 0, hi = 1E5;
        
        auto check = [&](real t) {
            Line l(s, s + vec * t);
            return distanceSS(l, l1) < r - eps || distanceSS(l, l2) < r - eps || distanceSS(l, l3) < r - eps;
        };
        if (!check(hi)) {
            return;
        }
        for (int t = 0; t < 100; t++) {
            real m = (lo + hi) / 2;
            if (check(m)) {
                hi = m;
            } else {
                lo = m;
            }
        }
        if (ans < 0 || ans > lo) {
            ans = lo;
        }
    };
    ang = o;
    for (int i = p; i >= 0; i--) {
        if (i == p) {
            work(a[i], o);
        } else {
            P u = o + (ang - o) / (ang.x - o.x) * (a[i].x - o.x);
            P v = o + (ang - o) / (ang.x - o.x) * (a[i + 1].x - o.x);
            if (u.y < a[i].y) {
                u = a[i];
            }
            P p;
            if (ang == o) {
                u = a[i];
                v = a[i + 1];
                p = u;
            } else if (parallel(Line(o, ang), Line(a[i], a[i + 1]))) {
                p = u;
            } else {
                p = lineIntersection(Line(o, ang), Line(a[i], a[i + 1]));
            }
            work(u, p);
            work(p, v);
        }
        if (ang == o || cross(a[i] - o, ang - o) > 0) {
            ang = a[i];
        }
    }
    ang = o;
    for (int i = p; i < n; i++) {
        if (i == p) {
            work(o, a[i + 1]);
        } else {
            P u = o + (ang - o) / (ang.x - o.x) * (a[i].x - o.x);
            P v = o + (ang - o) / (ang.x - o.x) * (a[i + 1].x - o.x);
            if (v.y < a[i + 1].y) {
                v = a[i + 1];
            }
            P p;
            if (ang == o) {
                u = a[i];
                v = a[i + 1];
                p = u;
            } else if (parallel(Line(o, ang), Line(a[i], a[i + 1]))) {
                p = u;
            } else {
                p = lineIntersection(Line(o, ang), Line(a[i], a[i + 1]));
            }
            work(u, p);
            work(p, v);
        }
        if (ang == o || cross(a[i + 1] - o, ang - o) < 0) {
            ang = a[i + 1];
        }
    }
    
    if (ans < 0) {
        std::cout << -1 << "\n";
    } else {
        std::cout << std::fixed << std::setprecision(10) << ans << "\n";
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7 1 0 2 2 4 2 5 5 6 0 9 4 12 3 14 0
2 13 -1 1 -1 1 1

output:

8.8994959366

result:

ok found '8.89950', expected '8.89900', error '0.00006'

Test #2:

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

input:

3 0 0 3 3 6 3 9 0
3 4 1 1 -1 1 1

output:

1.1213213436

result:

ok found '1.12132', expected '1.12132', error '0.00000'

Test #3:

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

input:

3 0 0 3 3 6 3 9 0
4 4 1 1 -1 1 1

output:

1.4142149766

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #4:

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

input:

3 0 0 3 3 6 3 9 0
4 4 1 1 1 1 1

output:

1.4142149766

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #5:

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

input:

3 0 0 3 3 6 3 9 0
8 4 1 1 1 1 1

output:

1.8284281247

result:

ok found '1.82843', expected '1.82843', error '0.00000'

Test #6:

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

input:

3 0 0 3 3 6 3 9 0
0 4 1 1 0 1 1

output:

1.5857878518

result:

ok found '1.58579', expected '1.58579', error '0.00000'

Test #7:

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

input:

3 0 0 3 3 6 3 9 0
0 4 1 1 1 1 1

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #8:

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

input:

2 10 10 30 40 60 60
50 40 30 10 -1 1 1

output:

3.9440976163

result:

ok found '3.94410', expected '3.94410', error '0.00000'

Test #9:

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

input:

5 0 80 40 0 60 60 100 0 120 40 160 60
0 140 20 20 -1 1 1

output:

7.2024212338

result:

ok found '7.20242', expected '7.20242', error '0.00000'

Test #10:

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

input:

5 0 80 40 0 60 60 100 0 120 40 160 60
0 140 20 20 0 1 1

output:

7.6393213430

result:

ok found '7.63932', expected '7.63932', error '0.00000'

Test #11:

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

input:

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

output:

2.0065749457

result:

ok found '2.00657', expected '2.00657', error '0.00000'

Test #12:

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

input:

9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4
0 -8 3 1 1 1 1

output:

2.8284285390

result:

ok found '2.82843', expected '2.82843', error '0.00000'

Test #13:

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

input:

9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4
-12 -8 3 1 1 1 1

output:

8.1514340011

result:

ok found '8.15143', expected '8.15143', error '0.00000'

Test #14:

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

input:

8 -4956 0 -413 0 413 1239 1239 0 1652 826 2478 826 3404 1239 3717 1239 5000 0
413 -1239 -1652 413 2 1 1

output:

2770.4882263583

result:

ok found '2770.48823', expected '2770.48822', error '0.00000'

Test #15:

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

input:

2 0 3 3 0 6 3
1 3 -1 1 0 1 1

output:

0.0000010000

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #16:

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

input:

20 1 11 4 1 5 14 6 8 8 8 9 1 12 14 14 12 17 8 21 6 25 1 27 8 29 4 35 5 37 16 38 17 39 16 45 9 47 4 48 11 49 2
6 21 -2 1 0 15 5

output:

4.7171575704

result:

ok found '4.71716', expected '4.71716', error '0.00000'

Test #17:

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

input:

20 2 10 4 4 6 13 9 3 10 12 11 5 12 0 14 15 15 10 17 20 19 8 21 4 28 18 29 7 32 10 36 2 39 0 40 5 41 6 42 18 47 2
33 34 -11 4 -3 13 1

output:

15.3538354002

result:

ok found '15.35384', expected '15.35383', error '0.00000'

Test #18:

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

input:

33 -4858 1505 -4750 252 -4377 2301 -4299 1512 -4124 4848 -3928 551 -3650 1782 -3242 163 -3241 4713 -2817 1286 -2753 2708 -1859 4013 -991 2481 -837 2253 356 669 385 4947 558 336 841 4286 1041 91 1122 3030 1371 4183 1456 1266 1632 844 1802 4762 2340 4087 2353 2421 2696 1915 3294 220 4405 3012 4413 481...

output:

43.6180615111

result:

ok found '43.61806', expected '43.61806', error '0.00000'

Test #19:

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

input:

20 0 11 4 18 5 0 9 5 10 17 12 2 13 0 16 11 18 3 19 5 21 3 25 19 31 2 32 6 34 13 35 9 37 20 42 0 45 12 46 14 47 4
38 9 -15 5 -1 15 3

output:

57.5750086442

result:

ok found '57.57501', expected '57.57501', error '0.00000'

Test #20:

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

input:

20 0 7 1 8 5 18 10 10 12 7 13 8 15 0 16 1 17 7 19 11 25 13 26 2 27 2 29 4 37 14 38 6 40 12 42 17 43 15 44 6 47 3
41 4 -14 1 6 5 5

output:

8.3683951787

result:

ok found '8.36840', expected '8.36839', error '0.00000'

Test #21:

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

input:

15 -4759 2812 -4596 3951 -4052 4157 -3244 779 -2591 4780 -1380 81 -839 3638 -757 1156 8 392 881 3169 1035 2070 1390 3818 1982 3218 2020 2830 2686 2080 3928 4241
1390 1388 -1229 398 439 4605 41

output:

100.1453774823

result:

ok found '100.14538', expected '100.14538', error '0.00000'

Test #22:

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

input:

100 2 144 10 36 12 238 14 286 17 461 19 257 20 174 25 6 32 96 38 199 52 451 59 304 61 372 64 17 65 426 70 432 76 40 77 253 79 382 82 164 84 408 94 208 99 386 102 434 103 482 104 428 111 95 112 192 114 381 117 285 124 259 130 289 131 402 133 462 136 10 138 367 147 500 150 365 153 145 156 267 157 299 ...

output:

34.4888005666

result:

ok found '34.48880', expected '34.48880', error '0.00000'

Test #23:

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

input:

100 13 43 14 384 16 276 22 343 26 375 28 453 29 369 40 265 41 153 45 81 51 446 58 58 62 388 65 187 73 109 77 167 79 59 98 316 104 257 105 133 112 68 120 345 133 95 144 290 145 70 146 375 152 118 160 362 166 75 167 479 168 48 176 141 178 45 181 339 183 355 184 261 188 221 189 267 196 108 207 263 211 ...

output:

0.0000000000

result:

wrong answer 1st numbers differ - expected: '-1.00000', found: '0.00000', error = '1.00000'