QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#805389#9869. Horizon ScanningjayketAC ✓62ms6092kbC++2321.0kb2024-12-08 16:24:282024-12-08 16:24:35

Judging History

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

  • [2024-12-08 16:24:35]
  • 评测
  • 测评结果:AC
  • 用时:62ms
  • 内存:6092kb
  • [2024-12-08 16:24:28]
  • 提交

answer

#include<bits/stdc++.h>

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = long double;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;

#ifndef ONLINE_JUDGE
#include "algo/debug.hpp"
#else
#define debug(...) (void)42
#endif

template<class T>
constexpr bool chmax(T& x, T y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

template<class T>
constexpr bool chmin(T& x, T y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

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);
    }
    constexpr friend Point operator+(Point a, const Point &b) {
        return a += b;
    }
    constexpr friend Point operator-(Point a, const Point &b) {
        return a -= b;
    }
    constexpr friend Point operator*(Point a, const T &b) {
        return a *= b;
    }
    constexpr friend Point operator/(Point a, const T &b) {
        return a /= b;
    }
    constexpr friend Point operator*(const T &a, Point b) {
        return b *= a;
    }
    constexpr friend bool operator==(const Point &a, const Point &b) {
        return a.x == b.x && a.y == b.y;
    }
    constexpr friend bool operator<(const Point& a, const Point& b) {
        return (a.x == b.x) ? a.y < b.y : a.x < b.x;
    }
    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>
f64 length(const Point<T> &p) {
    return sqrtl(square(p));
}

template<class T>
f64 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>
f64 distance(const Point<T> &a, const Point<T> &b) {
    return length(a - b);
}

template<class T>
f64 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>
f64 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 or (a.y == 0 and a.x > 0) ? 1 : -1;
}

template<class T>
bool compute(const Point<T>& a, const Point<T>& b) {
    if (sgn(a) == sgn(b)) {
        return cross(a, b) > 0;
    }
    return sgn(a) > sgn(b);
}

template<class T>
f64 angle(const Point<T>& p) {
    return std::atan2<f64>(p.y, p.x);
}

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

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 and std::min(l.a.x, l.b.x) <= p.x and p.x <= std::max(l.a.x, l.b.x) and std::min(l.a.y, l.b.y) <= p.y and p.y <= std::max(l.a.y, l.b.y);
}

template<class T>
bool pointOnLine(const Point<T> &p, const Line<T> &l) {
    return pointOnSegment(p, l) or pointOnSegment(l.a, Line(p, l.b)) or pointOnSegment(l.b, Line(p, l.a));
}

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++) {
        const auto &u = p[i];
        const auto &v = p[(i + 1) % n];
        if (u.x < a.x and v.x >= a.x and pointOnLineLeft(a, Line(v, u))) {
            t ^= 1;
        }
        if (u.x >= a.x and v.x < a.x and 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 {
            const auto &maxx1 = std::max(l1.a.x, l1.b.x);
            const auto &minx1 = std::min(l1.a.x, l1.b.x);
            const auto &maxy1 = std::max(l1.a.y, l1.b.y);
            const auto &miny1 = std::min(l1.a.y, l1.b.y);
            const auto &maxx2 = std::max(l2.a.x, l2.b.x);
            const auto &minx2 = std::min(l2.a.x, l2.b.x);
            const auto &maxy2 = std::max(l2.a.y, l2.b.y);
            const 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};
            }
        }
    }
    const auto &cp1 = cross(l2.a - l1.a, l2.b - l1.a);
    const auto &cp2 = cross(l2.a - l1.b, l2.b - l1.b);
    const auto &cp3 = cross(l1.a - l2.a, l1.b - l2.a);
    const auto &cp4 = cross(l1.a - l2.b, l1.b - l2.b);
    if ((cp1 > 0 and cp2 > 0) or (cp1 < 0 and cp2 < 0) or (cp3 > 0 and cp4 > 0) or (cp3 < 0 and cp4 < 0)) {
        return {0, Point<T>(), Point<T>()};
    }
    Point p = lineIntersection(l1, l2);
    if (cp1 != 0 and cp2 != 0 and cp3 != 0 and cp4 != 0) {
        return {1, p, p};
    } else {
        return {3, p, p};
    }
}

template<class T>
f64 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++) {
        const auto &u = p[i];
        const auto &v = p[(i + 1) % n];
        const auto &w = p[(i + 2) % n];
        const 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) and v != l.a and v != l.b) {
                if (cross(v - u, w - v) > 0) {
                    return false;
                }
            }
        } else {
            if (p1 != u and p1 != v) {
                if (pointOnLineLeft(l.a, Line(v, u)) or pointOnLineLeft(l.b, Line(v, u))) {
                    return false;
                }
            } else if (p1 == v) {
                if (l.a == v) {
                    if (pointOnLineLeft(u, l)) {
                        if (pointOnLineLeft(w, l) and pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, l) or 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)) and pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, Line(l.b, l.a)) or pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    }
                } else {
                    if (pointOnLineLeft(u, l)) {
                        if (pointOnLineLeft(w, Line(l.b, l.a)) or pointOnLineLeft(w, Line(u, v))) {
                            return false;
                        }
                    } else {
                        if (pointOnLineLeft(w, l) or 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(), [&](const auto & l1, const auto & l2) {
        const auto &d1 = l1.b - l1.a;
        const 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 (const auto &l : lines) {
        if (ls.empty()) {
            ls.push_back(l);
            continue;
        }
        while (!ps.empty() and !pointOnLineLeft(ps.back(), l)) {
            ps.pop_back();
            ls.pop_back();
        }
        while (!ps.empty() and !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() and !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());
}

template<class T>
T PolygonArea(const std::vector<Point<T>> &p) {
    T res = T(0);
    int n = p.size();
    for (int i = 0; i < n; i += 1) {
        res += cross(p[i], p[(i + 1) % n]);
    }
    return std::abs(res);
}

template<class T>
std::vector<Point<T>> getHull(std::vector<Point<T>> p) {
    std::vector<Point<T>>h, l;
    std::sort(p.begin(), p.end(), [&](const auto & a, const auto & b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    });
    p.erase(std::unique(p.begin(), p.end()), p.end());
    if (p.size() <= 1) {
        return p;
    }
    for (const auto & a : p) {
        while ((int)h.size() > 1 and cross(a - h.back(), a - h[(int)h.size() - 2]) <= 0) {
            h.pop_back();
        }
        while ((int)l.size() > 1 and cross(a - l.back(), a - l[(int)l.size() - 2]) >= 0) {
            l.pop_back();
        }
        l.push_back(a);
        h.push_back(a);
    }
    l.pop_back();
    std::reverse(h.begin(), h.end());
    h.pop_back();
    l.insert(l.end(), h.begin(), h.end());
    return l;
}

template<class T>
std::tuple<T, Point<T>, Point<T>> getLongest(const std::vector<Point<T>>& ret) {
    std::vector<Point<T>> p = getHull(ret);
    int n = p.size();

    T res = T(0);
    Point<T> a = Point<T>(), b = Point<T>();
    int x = 0, y = 0;
    for (int i = 0; i < n; i += 1) {
        if (p[i].y < p[x].y)x = i;
        if (p[i].y > p[y].y)y = i;
    }
    res = square(p[x] - p[y]);
    a = p[x], b = p[y];
    int i = x, j = y;
    do {
        if (cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) < 0) {
            i = (i + 1) % n;
        } else {
            j = (j + 1) % n;
        }
        if (square(p[i] - p[j]) > res) {
            res = square(p[i] - p[j]);
            a = p[i], b = p[j];
        }
    } while (i != x or j != y);
    return {res, a, b};
}

template<class T>
std::tuple<T, Point<T>, Point<T>> getClostest(std::vector<Point<T>> p) {
    std::sort(p.begin(), p.end(), [&](const auto & a, const auto & b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    });
    T res = std::numeric_limits<T>::max();
    Point<T> a = Point<T>(), b = Point<T>();
    int n = p.size();

    auto update = [&](const Point<T>& u, const Point<T>& v) {
        if (res > square(u - v)) {
            res = square(u - v);
            a = u;
            b = v;
        }
    };

    auto s = std::multiset < Point<T>, decltype([](const Point<T>& u, const Point<T>& v) {
        return u.y == v.y ? u.x < v.x : u.y < v.y;
    }) > ();
    std::vector<typename decltype(s)::const_iterator>its(n);
    for (int i = 0, f = 0; i < n; i += 1) {
        while (f < i and (p[i] - p[f]).x * (p[i] - p[f]).x >= res) {
            s.erase(its[f++]);
        }
        auto u = s.upper_bound(p[i]); {
            auto t = u;
            while (true) {
                if (t == s.begin()) {
                    break;
                }
                t = std::prev(t);
                update(*t, p[i]);
                if ((p[i] - *t).y * (p[i] - *t).y >= res) {
                    break;
                }
            }
        }{
            auto t = u;
            while (true) {
                if (t == s.end()) {
                    break;
                }
                if ((p[i] - *t).y * (p[i] - *t).y >= res) {
                    break;
                }
                update(*t, p[i]);
                t = std::next(t);
            }
        }
        its[i] = s.emplace_hint(u, p[i]);
    }

    return {res, a, b};
}

template<class T>
std::pair<T, std::vector<Point<T>>> rectCoverage(const std::vector<Point<T>>& p) {
    T res = std::numeric_limits<T>::max();
    std::vector<Point<T>>rect;
    std::array<int, 4>pos {};
    int n = p.size();
    if (n < 3) {
        return std::pair(res, rect);
    }
    for (int i = 0, r = 1, j = 1, q = 0; i < n; i += 1) {
        while (cross(p[(i + 1) % n] - p[i], p[(r + 1) % n] - p[i]) >= cross(p[(i + 1) % n] - p[i], p[r] - p[i])) {
            r = (r + 1) % n;
        }
        while (dot(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[i]) >= dot(p[(i + 1) % n] - p[i], p[j] - p[i])) {
            j = (j + 1) % n;
        }
        if (i == 0) {
            q = j;
        }
        while (dot(p[(i + 1) % n] - p[i], p[(q + 1) % n] - p[i]) <= dot(p[(i + 1) % n] - p[i], p[q] - p[i])) {
            q = (q + 1) % n;
        }
        T d = square(p[i] - p[(i + 1) % n]);
        T area = cross(p[(i + 1) % n] - p[i], p[r] - p[i]) * (dot(p[(i + 1) % n] - p[i], p[j] - p[i]) - dot(p[(i + 1) % n] - p[i], p[q] - p[i])) / d;
        if (area < res) {
            res = area;
            pos[0] = r;
            pos[1] = j;
            pos[2] = q;
            pos[3] = i;
        }
    }
    const auto& [r, j, q, i] = pos;
    Line<T> l1 = Line(p[i], p[(i + 1) % n]);
    Point t = p[(i + 1) % n] - p[i];
    Line<T> l2 = Line(p[r], p[r] + t);
    t = rotate(t);
    Line<T> l3 = Line(p[j], p[j] + t);
    Line<T> l4 = Line(p[q], p[q] + t);

    rect.push_back(lineIntersection(l1, l3));
    rect.push_back(lineIntersection(l1, l4));
    rect.push_back(lineIntersection(l2, l3));
    rect.push_back(lineIntersection(l2, l4));

    rect = getHull(rect);
    return std::pair(res, rect);
}

template<class T>
Point<T> triangleHeart(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
    return (A * square(B - C) + B * square(C - A) + C * square(A - B)) / (square(B - C) + square(C - A) + square(A - B));
}

template<class T>
Point<T> circumcenter(const Point<T>& a, const Point<T>& b, const Point<T>& c) {
    T D = 2 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
    assert(D != 0);
    Point<T> p;
    p.x = ((square(a) * (b.y - c.y) + (square(b) * (c.y - a.y)) + (square(c) * (a.y - b.y)))) / D;
    p.y = ((square(a) * (c.x - b.x) + (square(b) * (a.x - c.x)) + (square(c) * (b.x - a.x)))) / D;
    return p;
}

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

template<class T>
std::pair<Point<T>, T> cirlCoverage(std::vector<Point<T>> p) {
    for (int t = 0; t < 7; t += 1) {
        std::shuffle(p.begin(), p.end(), rng);
    }
    int n = p.size();
    Point<T> o = p[0];
    T r = T(0);
    for (int i = 1; i < n; i += 1) {
        if (length(o - p[i]) > r) {
            o = p[i];
            r = T(0);
            for (int j = 0; j < i; j += 1) {
                if (length(o - p[j]) > r) {
                    o = (p[i] + p[j]) / T(2);
                    r = length(o - p[i]);
                    for (int k = 0; k < j; k += 1) {
                        if (length(o - p[k]) > r) {
                            o = circumcenter(p[i], p[j], p[k]);
                            r = length(o - p[i]);
                        }
                    }
                }
            }
        }
    }
    return std::pair(o, r);
}

template<class F>
f64 integral(f64 l, f64 r, const F& f) {
    static constexpr f64 eps = 1e-9;
    auto simpson = [&](f64 l, f64 r) {
        return (f(l) + 4 * f((l + r) / 2) + f(r)) * (r - l) / 6;
    };
    auto func = [&](auto && func, f64 l, f64 r, f64 eps, f64 st) {
        f64 mid = (l + r) / 2;
        f64 sl = simpson(l, mid), sr = simpson(mid, r);
        if (std::abs(sl + sr - st) <= 15 * eps) {
            return (sl + sr + (sl + sr - st) / 15);
        }
        return func(func, l, mid, eps / 2, sl) + func(func, mid, r, eps / 2, sr);
    };
    return func(func, l, r, eps, simpson(l, r));
}

using P = Point<i64>;
using L = Line<i64>;
const f64 pi = std::acos(-1.l);

auto main() ->int32_t {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(13);

    auto solve = [&]() {
        int n, k;
        std::cin >> n >> k;

        std::vector<P>p(n);
        for (auto & c : p) {
            std::cin >> c;
        }

        if (n == k) {
            std::cout << 2 * pi << '\n';
        } else {
            f64 res = 0;
            std::sort(p.begin(), p.end(), [&](const auto & a, const auto & b) {
                if (sgn(a) == sgn(b)) {
                    return cross(a, b) > 0;
                }
                return sgn(a) > sgn(b);
            });

            auto f = [&](const P & a) {
                f64 r = angle(a);
                if (r < 0) {
                    r += 2 * pi;
                }
                return r;
            };

            // for (const auto & c : p) {
            //     std::cout << f(c) << ' ';
            // }
            // std::cout << '\n';

            for (int i = 0, j = k; i < n; i += 1, (j += 1) %= n) {
                f64 t = 0;
                if (j >= i) {
                    t = f(p[j]) - f(p[i]);
                } else {
                    t = 2 * pi - f(p[i]) + f(p[j]);
                }
                chmax(res, t);
            }
            std::cout << res << '\n';
        }
    };

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}


这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

5
1 1
0 1
8 2
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
4 2
-1 1
0 1
0 2
1 1
4 2
-1000000000 0
-998244353 1
998244353 1
1000000000 0
3 1
0 1
0 2
0 -1

output:

6.2831853071796
1.5707963267949
5.4977871437821
3.1415926545916
3.1415926535898

result:

ok 5 numbers

Test #2:

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

input:

10000
16 1
-10 -6
-5 -6
-4 9
-2 5
-2 10
1 -7
1 -5
1 6
3 1
4 -9
6 -10
6 -3
6 1
8 -5
8 -4
9 -4
17 4
-9 2
-8 -4
-8 -3
-8 -1
-6 -2
-6 -1
-6 8
-5 -8
-5 10
-4 8
-2 -8
4 -9
4 0
5 -3
8 -5
9 -2
10 10
10 6
-7 2
-4 6
-2 -7
-2 -1
-1 7
1 -9
1 8
3 -4
7 -4
9 -2
14 3
-9 10
-8 -10
-8 -8
-6 -7
-6 -5
-1 -7
-1 -2
0 -1
...

output:

1.6929914974863
2.5748634360663
4.6527582672535
2.7726331073839
5.7427658069090
4.8576989910204
3.4198923125949
2.8127999620848
6.2831853071796
6.2831853071796
5.1172807666698
6.1467827027786
3.8420890235375
2.3424967168195
3.4633432079864
6.2831853071796
5.9614347527829
3.3247034708523
5.2627749280...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 30ms
memory: 3940kb

input:

10000
19 7
-10 -6
-10 5
-3 0
-2 -5
-1 1
-1 6
0 3
0 7
1 9
3 -3
3 3
3 8
4 -1
5 8
6 -3
7 -5
7 4
8 10
9 -5
15 15
-9 -1
-8 6
-7 9
-6 -3
-4 -9
-1 -3
-1 8
1 -8
1 -7
3 -2
3 1
6 -9
7 -10
7 0
10 -9
10 3
-7 -1
-6 -2
-6 10
-5 2
-4 2
-3 -7
-2 -9
1 -3
3 4
7 7
15 4
-8 -8
-8 8
-7 0
-7 10
-6 -7
-5 6
-1 -3
-1 0
1 -2
...

output:

3.9269908169872
6.2831853071796
3.3602615994637
2.6779450445890
3.7703889400052
1.7625844687816
3.8402524783113
5.4977871437821
2.0344439357957
1.8157749899218
4.3471875305965
6.1412882525754
5.1760365893855
5.4655402613469
5.7690391512670
4.3662530168153
5.9947557486612
4.8922424801772
4.1719694801...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 29ms
memory: 3880kb

input:

10000
18 12
-10 -4
-10 7
-8 -10
-7 -4
-6 5
-6 7
-5 0
-2 -7
-1 2
-1 10
0 2
1 1
3 -2
5 3
5 5
6 -3
8 -3
9 -2
10 1
-10 -9
-7 -7
-5 2
-4 -7
-3 1
3 1
3 3
5 -4
9 2
9 6
11 2
-8 1
-8 6
-7 -2
-6 0
-5 0
-1 -9
2 -8
3 5
6 0
10 -2
10 6
20 9
-10 -6
-10 6
-9 -8
-7 5
-6 -4
-4 -8
-2 -10
-2 -3
-2 4
-1 1
2 -5
3 -2
5 -6...

output:

4.9097845402346
1.9756881130800
1.9868608325187
3.9269908169872
3.6977588837102
6.2831853071796
6.1412882525754
6.1938713141864
5.8053542521875
6.2528915472608
5.7288778109780
3.0900918426386
1.8925468811915
5.6341897481831
2.8966139904629
6.2831853071796
2.9147938055359
6.1476575931941
1.9513027039...

result:

ok 10000 numbers

Test #5:

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

input:

10000
19 7
-10 -1
-8 2
-7 -10
-6 6
-4 7
-3 -5
-3 1
-3 8
-2 4
-1 -7
0 -8
0 9
1 -10
2 1
2 3
3 5
6 -4
10 2
10 3
14 10
-8 2
-6 0
-5 -10
-5 10
-4 7
-3 -6
-2 -6
1 4
1 6
2 -1
3 -6
8 -4
9 -10
10 -1
12 8
-9 5
-7 2
-4 2
0 -2
0 5
1 6
3 2
4 9
5 5
7 -6
9 -9
9 2
19 12
-10 -10
-10 2
-9 -6
-8 2
-7 -5
-6 8
-4 1
-1 -...

output:

3.2393195609485
5.2757052418767
5.3003915839323
5.3871299226082
5.8883941874798
4.1173193566791
1.1383885512244
1.5152978215492
6.1476575931941
6.1588303126328
2.5748634360663
5.9401613667589
1.6085142792618
4.6099451268776
5.0711596506553
4.2345579253926
3.7905882125863
4.0376480381611
3.9160022483...

result:

ok 10000 numbers

Test #6:

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

input:

10000
11 10
-10 -1
-9 4
-9 10
-7 -7
-5 4
-4 -1
-2 -10
0 -7
0 5
3 3
3 5
12 12
-9 6
-9 8
-3 -2
-2 2
0 -4
1 0
2 -3
3 5
5 -2
7 -1
10 3
10 9
14 12
-10 0
-9 -3
-9 1
-9 10
-8 -1
-8 7
-6 -1
-1 -6
-1 2
1 -1
3 -7
4 9
9 -3
10 1
10 4
-9 -3
-7 -1
-6 -10
-3 -2
-3 7
2 -2
2 3
5 2
6 9
9 6
10 2
-9 -9
-9 6
-8 3
-5 -9
...

output:

6.1378752965439
6.2831853071796
6.1180366297650
3.2003484763055
2.6537562149302
6.2537820189756
3.6052402625906
3.5598169831690
1.5091461561556
5.9275494228788
6.2587998980069
2.6224465393433
4.3938333032966
5.4977871437821
4.2487413713839
5.4977871437821
4.6292477484962
3.5464844398749
6.0048856481...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 34ms
memory: 3940kb

input:

10000
14 1
-100 13
-96 -31
-82 -92
-77 -98
-50 1
-14 -57
-14 -31
-11 64
-8 75
9 68
25 100
54 -36
59 13
93 31
19 19
-76 -39
-60 95
-51 18
-39 11
-21 -46
-6 -94
-5 83
-3 -34
-3 72
0 -55
3 79
14 17
23 -88
32 37
50 70
61 -5
62 -43
84 -100
97 -50
13 7
-99 -63
-68 -87
-24 62
-20 -18
-2 -66
7 -49
13 -21
15...

output:

1.2713093974613
6.2831853071796
5.2225147207365
6.0030657035689
3.9258721354647
5.5465289950921
3.2103149237117
3.0399300499237
4.2275317817944
3.0320196657369
2.1912152338182
3.0390080903677
4.3313271506355
6.2831853071796
5.1100022650512
2.9463140260615
5.1760365893855
5.6991835713711
2.0611798650...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 34ms
memory: 3856kb

input:

100
1413 755
-30 -30
-30 -28
-30 -27
-30 -26
-30 -21
-30 -12
-30 -10
-30 -8
-30 -5
-30 -1
-30 2
-30 4
-30 7
-30 9
-30 17
-30 19
-30 20
-30 23
-30 24
-30 30
-29 -29
-29 -23
-29 -15
-29 0
-29 4
-29 5
-29 9
-29 10
-29 11
-29 12
-29 14
-29 16
-29 17
-29 22
-29 27
-29 28
-28 -28
-28 -25
-28 -23
-28 -22
-...

output:

3.5891126287470
2.9797552223514
0.2837941092083
2.0350277068911
4.8879811423349
1.0040671092714
4.7457099762629
5.3255963292592
4.3102749647329
5.6033836794138
1.5798050920853
4.3296454705391
5.5472220967941
1.4601391056210
1.5310445513990
2.8716749317081
2.6325789668605
3.1240505935324
0.6805212246...

result:

ok 100 numbers

Test #9:

score: 0
Accepted
time: 37ms
memory: 4084kb

input:

20
9045 8319
-1000 -986
-1000 -683
-1000 -430
-1000 -292
-1000 53
-1000 667
-999 -855
-999 -350
-999 -174
-999 -51
-999 -43
-999 235
-999 465
-999 530
-998 -997
-998 -311
-998 21
-998 44
-998 182
-997 -313
-997 -195
-997 -13
-997 412
-997 425
-996 -542
-996 -348
-996 -126
-996 -59
-996 -40
-996 84
-...

output:

5.9115110039040
3.7438685151377
2.5384828583153
2.1599673588579
4.2950377095723
4.7716744747962
4.6824078126019
5.0789843941746
1.6008018214107
3.3404025456367
3.3687925282503
2.1130160282301
4.8553994101327
4.3240010532705
0.1078535610706
0.1798211241778
5.3766547606521
4.4495660239030
4.3944016651...

result:

ok 20 numbers

Test #10:

score: 0
Accepted
time: 39ms
memory: 5648kb

input:

1
166347 18723
-1000 -979
-1000 -975
-1000 -928
-1000 -914
-1000 -898
-1000 -889
-1000 -876
-1000 -873
-1000 -858
-1000 -840
-1000 -838
-1000 -801
-1000 -783
-1000 -744
-1000 -738
-1000 -733
-1000 -713
-1000 -712
-1000 -695
-1000 -689
-1000 -680
-1000 -675
-1000 -671
-1000 -646
-1000 -643
-1000 -608...

output:

0.8514491789805

result:

ok found '0.8514492', expected '0.8514492', error '0.0000000'

Test #11:

score: 0
Accepted
time: 36ms
memory: 5948kb

input:

1
154903 84960
-1000 -979
-1000 -965
-1000 -956
-1000 -945
-1000 -920
-1000 -901
-1000 -878
-1000 -860
-1000 -858
-1000 -709
-1000 -693
-1000 -648
-1000 -619
-1000 -602
-1000 -579
-1000 -474
-1000 -473
-1000 -454
-1000 -443
-1000 -427
-1000 -407
-1000 -403
-1000 -384
-1000 -351
-1000 -279
-1000 -244...

output:

3.5389266853832

result:

ok found '3.5389267', expected '3.5389267', error '0.0000000'

Test #12:

score: 0
Accepted
time: 41ms
memory: 5824kb

input:

1
158037 96343
-1000 -1000
-1000 -905
-1000 -881
-1000 -833
-1000 -804
-1000 -803
-1000 -782
-1000 -775
-1000 -765
-1000 -759
-1000 -756
-1000 -748
-1000 -722
-1000 -674
-1000 -669
-1000 -630
-1000 -610
-1000 -573
-1000 -443
-1000 -411
-1000 -409
-1000 -403
-1000 -388
-1000 -366
-1000 -349
-1000 -33...

output:

3.9720287783259

result:

ok found '3.9720288', expected '3.9720288', error '0.0000000'

Test #13:

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

input:

10000
17 12
-853202371 684059854
-659446544 -924219854
-418025687 117998679
-399757126 -365708913
-331597239 -270896799
-204989763 869548983
-118492298 963842298
-77481232 672198731
45930201 -58234380
52605147 -900097542
78371985 940503934
235210685 595759114
391284089 234315077
416229789 -827244230...

output:

5.3985251100344
5.3739078748564
1.1735781728742
1.5443652595084
3.7782886494031
3.5704715868525
6.2829748588362
5.0959252028151
2.9875782465509
2.3055665058015
3.3907841641820
5.7854732381281
4.8109636122640
0.9567574180421
4.6294317309773
4.7995080628836
4.1702889055908
5.7394776963039
6.1210294479...

result:

ok 10000 numbers

Test #14:

score: 0
Accepted
time: 39ms
memory: 3848kb

input:

1000
133 108
-994106086 710243426
-991027749 -548437545
-983318226 -917527783
-943673956 -368162275
-935819096 616077188
-928022346 487569673
-924213856 -369318351
-914827619 426646545
-883935180 590882141
-870015071 -270471333
-834927107 -211343853
-829266515 354007200
-788041913 -60481736
-7822837...

output:

5.7428017921432
1.9153642398418
3.8043457981080
1.7919162705311
3.1695206706352
6.0786462146156
3.7860674595106
3.6659690726879
6.2265834529704
5.9021521926104
5.9443157092957
0.7151676870431
3.8315742529772
1.2228457184603
2.5984264669494
5.5473289205077
4.0791947427722
0.7042209930056
5.8578224268...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 45ms
memory: 3864kb

input:

100
1367 924
-999416811 990355566
-997656126 346133696
-997071616 -657387469
-996176051 12622726
-995720693 334093112
-995478093 891631278
-994503890 341858449
-994297596 499383911
-993234202 533518057
-991636838 -4170504
-990563582 -407186200
-989454027 653116272
-989132124 -780605454
-988073521 -1...

output:

4.5051534906177
2.7125589326275
5.8396785809820
6.0229771114526
0.4616060431014
0.9869912332125
1.3219708488343
1.9258417458381
5.5086083533499
4.6463553312979
2.2876774102077
2.1848725877963
4.8094091918068
0.4770789902411
0.5563416050088
1.0936191641533
5.1827145536064
3.1131846618087
4.3802339550...

result:

ok 100 numbers

Test #16:

score: 0
Accepted
time: 43ms
memory: 4156kb

input:

10
13806 4955
-999669776 933068103
-999542354 721337508
-999499427 357140594
-999429088 -925180511
-999334813 -145726169
-999291694 -886327684
-999281647 811188099
-999145269 860687107
-998961821 -979442436
-998769313 446186367
-998591455 658309173
-998539751 -569480843
-998479467 279850955
-9984754...

output:

2.4170804680340
6.1611922290787
3.9600203768422
3.9943617929046
2.5515508361555
0.5227238367810
4.0978438278542
6.2103826631589
5.9817280292540
0.7772236858906

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 37ms
memory: 4992kb

input:

1
112596 94970
-999980219 399324466
-999932413 952114487
-999894556 -951211102
-999891030 -996222974
-999864824 412806264
-999853190 -269700371
-999845814 -23906803
-999841507 -459154880
-999825178 716247149
-999761774 -154047106
-999729655 -171480333
-999709604 -666447277
-999704754 -22442485
-9996...

output:

5.4425938793439

result:

ok found '5.4425939', expected '5.4425939', error '0.0000000'

Test #18:

score: 0
Accepted
time: 53ms
memory: 5788kb

input:

1
161568 13252
-999991243 -113889211
-999976572 -361096764
-999970140 -505012445
-999960654 600963873
-999959339 -269932510
-999956568 734634576
-999941447 716485764
-999940305 64397798
-999939982 746532931
-999939921 995002380
-999932747 185078659
-999927136 585216518
-999914684 898656539
-99990452...

output:

0.6424745906865

result:

ok found '0.6424746', expected '0.6424746', error '0.0000000'

Test #19:

score: 0
Accepted
time: 62ms
memory: 6092kb

input:

1
186192 126483
-999998234 974001047
-999976292 -133179660
-999967957 112862981
-999957851 70030467
-999951528 743907713
-999931316 66002112
-999907988 888991267
-999905412 470798211
-999903986 -103943462
-999900422 255729004
-999898174 917068198
-999884392 -183592605
-999880179 -650076162
-99987469...

output:

4.4012456841190

result:

ok found '4.4012457', expected '4.4012457', error '0.0000000'

Test #20:

score: 0
Accepted
time: 37ms
memory: 3912kb

input:

1000
133 9
-10 -839744900
-10 -620593257
-10 -322048342
-10 578093727
-10 898998949
-9 -833794004
-9 -704882916
-9 -570204575
-9 -506146571
-9 -109555290
-9 309734100
-9 396668416
-8 -928874025
-8 376566668
-8 596463598
-8 600491164
-8 894775141
-7 -281322833
-7 49984651
-7 154512939
-7 205573228
-7...

output:

3.1415925828878
6.2831852482137
3.1415926144250
3.1415911740814
6.2831852702918
6.2831852953163
3.1415926492294
6.2831853036701
3.1415926401616
6.2831852506759
6.2831852816483
3.1415927591869
3.1415926453706
3.1415926237560
3.1415926152115
6.2831852733151
3.1415926493760
3.1415926537342
3.1415926532...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 31ms
memory: 4416kb

input:

5
23120 8224
-10 -999575056
-10 -997485895
-10 -995458183
-10 -986953157
-10 -985268102
-10 -983223383
-10 -980910524
-10 -980404283
-10 -973605147
-10 -972441960
-10 -972440422
-10 -969122114
-10 -965754004
-10 -964812113
-10 -964558462
-10 -963159275
-10 -962972564
-10 -962085557
-10 -961552443
-1...

output:

3.1415926423514
3.1415926312424
3.1415926068008
3.1415926493953
6.2831852722069

result:

ok 5 numbers

Test #22:

score: 0
Accepted
time: 22ms
memory: 4684kb

input:

1
99995 60000
1 100001
1 100002
1 100003
1 100004
1 100005
1 100006
1 100007
1 100008
1 100009
1 100010
1 100011
1 100012
1 100013
1 100014
1 100015
1 100016
1 100017
1 100018
1 100019
1 100020
1 100021
1 100022
1 100023
1 100024
1 100025
1 100026
1 100027
1 100028
1 100029
1 100030
1 100031
1 10003...

output:

6.2831853069018

result:

ok found '6.2831853', expected '6.2831853', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed