QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55302#1343. Zombie LandckisekiCompile Error//C++6.0kb2022-10-13 01:59:082022-10-13 01:59:11

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-13 01:59:11]
  • Judged
Show
  • [2022-10-13 01:59:08]
  • Submitted

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const long double eps = 1e-10;

// using PT = complex<int64_t>;
using lld = int64_t;
struct PT {
    int64_t x, y;
    PT(int64_t t_x, int64_t t_y) : x(t_x), y(t_y) {}
};
static constexpr lld real(PT &p) {
    return p.x;
}
static constexpr lld imag(PT &p) {
    return p.y;
}
static PT operator-(const PT &a, const PT &b) {
    return {a.x - b.x, a.y - b.y};
}
int sgn(lld x) {
    return (x > 0) - (x < 0);
}
lld cross(PT a, PT b) {
    return a.x * b.y - a.y * b.x;
    // 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)
#define absurd() do { \
    cout << "P = " << P << endl; \
    cout << "V = "; \
    for (int i = 0; i < n; i++) cout << V[i] << ' '; \
    cout << endl; \
} while (0)

int Rtan(PT P, int n, PT *V) {
    if (n == 1)
        return 0;
    int a, b, c;
    int upA, dnC;
    if (below(P, V[1], V[0]) && !above(P, V[n-1], V[0]))
        return 0;
    int cnt = 0;
    for (a = 0, b = n;;) {
        c = (a + b) / 2;
        if (c == b || c == a) if (++cnt >= 3) absurd();
        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;
            }
        }
    }
    assert (false);
}

int Ltan(PT P, int n, PT *V) {
    if (n == 1)
        return 0;
    int a, b, c;
    int dnA, dnC;
    if (above(P, V[n - 1], V[0]) && !below(P, V[1], V[0]))
        return 0;
    int cnt = 0;
    for (a = 0, b = n;;) {
        c = (a + b) / 2;
        dnC = below(P, V[c + 1], V[c]);
        if (c == b || c == a) if (++cnt >= 3) absurd();
        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;
            }
        }
    }
    assert (false);
}

void build(vector<PT> &dots) {
    if (dots.size() <= 1) return;
    sort(dots.begin(), dots.end(), [](PT a, PT b) {
        if (real(a) != real(b)) return real(a) < real(b);
        return imag(a) < 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() {
    // freopen("i.in", "r", stdin);
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    int xz, vz;
    cin >> xz >> vz;

    bool cond = n==190408 && xz==767167456 && vz==-668935825;

    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 " << v << ' ' << x << endl;
        } else if (x > xz) {
            R.emplace_back(x, v, i);
            // cerr << "R " << v << ' ' << x << 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());
        if (cond) cout << cv.size() << endl;
        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());
        if (cond) cout << cv.size() << endl;
        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;
            }
        }
    }
        if (cond) return 0;

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

Details 

answer.code: In function ‘int Rtan(PT, int, PT*)’:
answer.code:36:20: error: no match for ‘operator<<’ (operand types are ‘std::basic_ostream<char>’ and ‘PT’)
   36 |     cout << "P = " << P << endl; \
      |     ~~~~~~~~~~~~~~ ^~ ~
      |          |            |
      |          |            PT
      |          std::basic_ostream<char>
answer.code:52:47: note: in expansion of macro ‘absurd’
   52 |         if (c == b || c == a) if (++cnt >= 3) absurd();
      |                                               ^~~~~~
In file included from /usr/include/c++/11/istream:39,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:2:
/usr/include/c++/11/ostream:108:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_CharT, _Traits>::__ostream_type& (*)(std::basic_ostream<_CharT, _Traits>::__ostream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]’
  108 |       operator<<(__ostream_type& (*__pf)(__ostream_type&))
      |       ^~~~~~~~
/usr/include/c++/11/ostream:108:36: note:   no known conversion for argument 1 from ‘PT’ to ‘std::basic_ostream<char>::__ostream_type& (*)(std::basic_ostream<char>::__ostream_type&)’ {aka ‘std::basic_ostream<char>& (*)(std::basic_ostream<char>&)’}
  108 |       operator<<(__ostream_type& (*__pf)(__ostream_type&))
      |                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/ostream:117:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_CharT, _Traits>::__ios_type& (*)(std::basic_ostream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>; std::basic_ostream<_CharT, _Traits>::__ios_type = std::basic_ios<char>]’
  117 |       operator<<(__ios_type& (*__pf)(__ios_type&))
      |       ^~~~~~~~
/usr/include/c++/11/ostream:117:32: note:   no known conversion for argument 1 from ‘PT’ to ‘std::basic_ostream<char>::__ios_type& (*)(std::basic_ostream<char>::__ios_type&)’ {aka ‘std::basic_ios<char>& (*)(std::basic_ios<char>&)’}
  117 |       operator<<(__ios_type& (*__pf)(__ios_type&))
      |                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
/usr/include/c++/11/ostream:127:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]’
  127 |       operator<<(ios_base& (*__pf) (ios_base&))
      |       ^~~~~~~~
/usr/include/c++/11/ostream:127:30: note:   no known conversion for argument 1 from ‘PT’ to ‘std::ios_base& (*)(std::ios_base&)’
  127 |       operator<<(ios_base& (*__pf) (ios_base&))
      |                  ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/11/ostream:166:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]’
  166 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:166:23: note:   no known conversion for argument 1 from ‘PT’ to ‘long int’
  166 |       operator<<(long __n)
      |                  ~~~~~^~~
/usr/include/c++/11/ostream:170:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]’
  170 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:170:32: note:   no known conversion for argument 1 from ‘PT’ to ‘long unsigned int’
  170 |       operator<<(unsigned long __n)
      |                  ~~~~~~~~~~~~~~^~~
/usr/include/c++/11/ostream:174:7: note: candidate: ‘std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]’
  174 |       operator<<(bool __n)
      |       ^~~~~~~~
/usr/include/c++/11/ostream:174:23: note:   no known conversion for argument 1 from ‘PT’ to ‘bool’
  174 |       operator<<(bool __n)
      |                  ~~~~~^~~
In file included from /usr/include/c++/11/ostream:853,
                 from /usr/include/c++/11/istream:...
English 繁體中文 简体中文

Server Time: 2025-02-08 18:18:22 | OpenSource Project