QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55288#1343. Zombie LandckisekiWA 2ms3920kbC++4.9kb2022-10-12 22:53:172022-10-12 22:53:18

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 22:53:18]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3920kb
  • [2022-10-12 22:53:17]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

const long double eps = 1e-10;

using PT = complex<int64_t>;
using lld = int64_t;
int sgn(lld x) {
    return (x > 0) - (x < 0);
}
lld cross(PT a, PT b) {
    return imag(conj(a) * b);
}
int ori(PT a, PT b, PT c) {
    return sgn(cross(b - a, c - a));
}

#define above(P, Vi, Vj) (ori(P, Vi, Vj) > 0)
#define below(P, Vi, Vj) (ori(P, Vi, Vj) < 0)

int Rtan(PT P, int n, PT *V) {
    int a, b, c;
    int upA, dnC;
    if (below(P, V[1], V[0]) && !above(P, V[n-1], V[0]))
        return 0;
    for (a = 0, b = n;;) {
        c = (a + b) / 2;
        dnC = below(P, V[c+1], V[c]);
        if (dnC && !above(P, V[c-1], V[c]))
            return c;
        upA = above(P, V[a+1], V[a]);
        if (upA) {
            if (dnC) {
                b = c;
            } else {
                if (above(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        } else {
            if (!dnC) {
                a = c;
            } else {
                if (below(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        }
    }
}

int Ltan(PT P, int n, PT *V) {
    int a, b, c;
    int dnA, dnC;
    if (above(P, V[n - 1], V[0]) && !below(P, V[1], V[0]))
        return 0;
    for (a = 0, b = n;;) {
        c = (a + b) / 2;
        dnC = below(P, V[c + 1], V[c]);
        if (above(P, V[c - 1], V[c]) && !dnC)
            return c;
        dnA = below(P, V[a + 1], V[a]);
        if (dnA) {
            if (!dnC) {
                b = c;
            } else {
                if (below(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        } else {
            if (dnC) {
                a = c;
            } else {
                if (above(P, V[a], V[c]))
                    b = c;
                else
                    a = c;
            }
        }
    }
}

#define MP make_pair
void build(vector<PT> &dots) {
    sort(dots.begin(), dots.end(), [](PT a, PT b) {
        return MP(real(a), imag(a)) < MP(real(b), imag(b));
    });
    vector<PT> ans(1, dots[0]);
    for (int ct = 0; ct < 2; ++ct, reverse(dots.begin(), dots.end())) {
        for (int i = 1, t = ans.size(); i < dots.size(); i++) {
            while (ans.size() > t && ori(
                        ans[ans.size() - 2], ans.back(), dots[i]) <= 0)
                ans.pop_back();
            ans.emplace_back(dots[i]);
        }
        ans.pop_back(), ans.swap(dots);
    }
}
long double slope(PT a, PT b) {
    if (real(a) == real(b)) {
        return -1e9;
    } else {
        return -(imag(a) - imag(b)) / (long double)(real(a) - real(b));
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    int xz, vz;
    cin >> xz >> vz;

    vector<tuple<int,int,int>> L, R;
    for (int i = 0; i < n; i++) {
        int x, v;
        cin >> x >> v;
        v -= vz;
        if (x < xz) {
            L.emplace_back(x, v, i);
            // cerr << "L " << x << ' ' << v << endl;
        } else if (x > xz) {
            R.emplace_back(x, v, i);
            // cerr << "R " << x << ' ' << v << endl;
        } else
            __builtin_unreachable();
    }

    // cerr << fixed << setprecision(3);

    vector<long double> ans(n, -1);
    {
        vector<PT> cv;
        for (auto [x, v, id]: L) {
            cv.emplace_back(v, x);
        }
        cv.emplace_back(0, xz);
        // build(cv);
        cv.emplace_back(cv.front());
        for (auto [x, v, id]: R) {
            // for (int j = 0; j < cv.size(); j++) {
            for (int j: {
                Ltan({v, x}, cv.size()-1, cv.data()),
                Rtan({v, x}, cv.size()-1, cv.data())
            }) {
                long double s = slope({v,x}, cv[j]);
                if (s < 0) continue;
                if (ans[id] < -eps || ans[id] > s)
                    ans[id] = s;
            }
        }
    }
    {
        vector<PT> cv;
        for (auto [x, v, id]: R) {
            cv.emplace_back(v, x);
        }
        cv.emplace_back(0, xz);
        // build(cv);
        cv.emplace_back(cv.front());
        for (auto [x, v, id]: L) {
            // for (int j = 0; j < cv.size(); j++) {
            for (int j: {
                Ltan({v, x}, cv.size()-1, cv.data()),
                Rtan({v, x}, cv.size()-1, cv.data())
            }) {
                long double s = slope({v,x}, cv[j]);
                if (s < 0) continue;
                if (ans[id] < -eps || ans[id] > s)
                    ans[id] = s;
            }
        }
    }

    cout << fixed << setprecision(15);
    for (int i = 0; i < n; i++) {
        if (ans[i] < -eps) {
            cout << -1 << '\n';
        } else {
            cout << ans[i] << '\n';
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3764kb

input:

6
3 1
-5 0
5 0
-4 -3
0 -2
6 -3
2 -1

output:

3.666666666666667
2.000000000000000
-1
6.000000000000000
0.750000000000000
2.000000000000000

result:

ok 6 numbers

Test #2:

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

input:

5
31415 -926
5358 979
323846 26
-433832 7950
288 -4
-1971 -69

output:

13.678215223097113
95.618122160524987
52.416291122127084
33.760303687635575
38.956826137689615

result:

ok 5 numbers

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3920kb

input:

972
98740224 301565350
897445571 19067267
-528259301 772813962
88724382 432443246
668138287 561147750
-111697007 795680328
716395194 388109596
-289144978 72929322
-935429651 690324478
632898250 -359347321
-388094843 -753263424
416481084 91553128
460683861 290773570
445572029 -788653120
-239712630 23...

output:

1.891490710947661
2.240893597101047
3.495350335602818
5.652284210575848
1.265131341112392
3.235353182864579
22.030175955967517
3.823549717935804
1.025611428720796
-1
4.347347349179602
2.051577374868619
0.623664335435539
5.292181684594715
0.871977004104281
-1
-1
3.181994956147331
3.372933703270793
3....

result:

wrong answer 1st numbers differ - expected: '0.8555381', found: '1.8914907', error = '1.0359527'