QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381950#784. 旋转卡壳Isrothy100 ✓144ms34008kbC++2320.8kb2024-04-07 22:28:112024-09-24 16:56:41

Judging History

你现在查看的是测评时间为 2024-09-24 16:56:41 的历史记录

  • [2024-10-16 12:20:56]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:143ms
  • 内存:34080kb
  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-09-24 16:56:41]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:144ms
  • 内存:34008kb
  • [2024-09-24 16:55:39]
  • hack成功,自动添加数据
  • (/hack/888)
  • [2024-07-31 21:54:33]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:176ms
  • 内存:34016kb
  • [2024-07-31 21:52:32]
  • hack成功,自动添加数据
  • (/hack/764)
  • [2024-07-31 21:49:06]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:143ms
  • 内存:34168kb
  • [2024-07-31 21:47:53]
  • hack成功,自动添加数据
  • (/hack/763)
  • [2024-05-30 09:01:38]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:148ms
  • 内存:34332kb
  • [2024-05-30 09:00:15]
  • hack成功,自动添加数据
  • (/hack/642)
  • [2024-04-07 22:28:11]
  • 评测
  • 测评结果:100
  • 用时:144ms
  • 内存:34080kb
  • [2024-04-07 22:28:11]
  • 提交

answer

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <functional>
#include <numeric>
#include <optional>
#include <span>
#include <stdexcept>
#include <variant>
#include <vector>
constexpr double EPS = 1e-10;
constexpr int sign(double x) {
    return x < -EPS ? -1 : EPS < x;
}
constexpr double sqr_diff(double a, double b) {
    return (a + b) * (a - b);
}
struct Point {
    double x = 0, y = 0;
    Point() = default;
    Point(double x, double y) : x(x), y(y){};
    auto len2() const {
        return x * x + y * y;
    }
    auto len() const {
        return std::hypot(x, y);
    }
    Point operator-() const {
        return {-x, -y};
    }
    Point operator*(double k) const {
        return {x * k, y * k};
    }
    Point operator/(double k) const {
        return {x / k, y / k};
    }
    Point unit() const {
        return *this / len();
    }
    Point normal() const {
        return {-y, x};
    }
    auto angle() const {
        return std::atan2(y, x);
    }
};
using Vector = Point;
using Line = std::pair<Point, Point>;
using Segment = Line;
using Circle = std::pair<Point, double>;
using Polygon = std::vector<Point>;
using Triangle = std::tuple<Point, Point, Point>;
Vector operator+(const Vector &a, const Vector &b) {
    return {a.x + b.x, a.y + b.y};
}
Vector operator-(const Vector &a, const Vector &b) {
    return {a.x - b.x, a.y - b.y};
}
Vector operator*(double k, const Vector &a) {
    return {a.x * k, a.y * k};
}
auto operator==(const Point &A, const Point &B) {
    return sign((A - B).len()) == 0;
}
auto dot(const Vector &a, const Vector &b) {
    return a.x * b.x + a.y * b.y;
}
auto det(const Vector &a, const Vector &b) {
    return a.x * b.y - a.y * b.x;
}
auto middle(const Point &A, const Point &B) {
    return 0.5 * (A + B);
}
auto vec(const Line &l) {
    return l.second - l.first;
}
auto len(const Segment &s) {
    return vec(s).len();
}
auto len2(const Segment &s) {
    return vec(s).len2();
}
auto angle(const Vector &a, const Vector &b) {
    auto tmp = a.len() * b.len();
    return sign(sqrt(tmp)) == 0 ? 0 : acos(dot(a, b) / tmp);
}
enum class Side : int { left = -1, on = 0, right = 1 };
auto side_of_line(const Point &P, const Line &l) {
    const auto &[A, B] = l;
    return Side(sign(det(P - A, B - A)));
}
auto projection(const Point &P, const Line &l) {
    const auto &[A, B] = l;
    Vector v = B - A;
    return A + dot(v, P - A) * v / v.len2();
}
auto symmetry(const Point &P, const Line &l) {
    return 2 * projection(P, l) - P;
}
auto point_line_distance(const Point &P, const Line &l) {
    const auto &[A, B] = l;
    Vector v1 = B - A, v2 = P - A;
    return std::fabs(det(v1, v2) / v1.len());
}
auto point_on_segment(const Point &P, const Segment &s) {
    const auto &[A, B] = s;
    return side_of_line(P, {A, B}) == Side::on && sign(dot(A - P, B - P)) <= 0;
}
auto point_segment_distance(const Point &P, const Segment &s) {
    const auto &[A, B] = s;
    auto v1 = B - A, v2 = P - A, v3 = P - B;
    if (sign(dot(v1, v2)) < 0) {
        return v2.len();
    }
    if (sign(dot(v1, v3)) > 0) {
        return v3.len();
    }
    return det(v1, v2) / v1.len();
}
auto parallel(const Line &l1, const Line &l2) {
    return sign(det(vec(l1), vec(l2))) == 0;
}
enum class LineLineRelation { parallel, identical, intersecting };
auto line_intersection(const Line &l1, const Line &l2)
    -> std::pair<LineLineRelation, std::optional<Point>> {
    const auto &[A, B] = l1;
    const auto &[C, D] = l2;
    if (parallel(l1, l2)) {
        if (side_of_line(A, l2) == Side::on) {
            return {LineLineRelation::identical, std::nullopt};
        }
        return {LineLineRelation::parallel, std::nullopt};
    }
    double s1 = det(D - A, C - A);
    double s2 = det(C - B, D - B);
    return {LineLineRelation::intersecting, A + (B - A) * (s1 / (s1 + s2))};
}
enum class SegmentSegmentRelation { disjoint, intersecting, touching };
auto segment_intersection(const Segment &s1, const Segment &s2)
    -> std::pair<SegmentSegmentRelation, std::optional<Point>> {
    const auto &[A, B] = s1;
    const auto &[C, D] = s2;
    auto [relation, p] = line_intersection(s1, s2);
    switch (relation) {
        using enum LineLineRelation;
        case parallel:
            return {SegmentSegmentRelation::disjoint, std::nullopt};
        case identical: {
            if (sign(dot(C - A, C - B)) <= 0 || sign(dot(D - A, D - B)) <= 0
                || sign(dot(A - C, A - D)) <= 0 || sign(dot(B - C, B - D)) <= 0) {
                return {SegmentSegmentRelation::touching, std::nullopt};
            }
            return {SegmentSegmentRelation::disjoint, std::nullopt};
        }
        case intersecting: {
            auto O = p.value();
            if (sign(dot(O - A, O - A)) <= 0 && sign(dot(O - C, O - D)) <= 0) {
                return {SegmentSegmentRelation::intersecting, O};
            }
            return {SegmentSegmentRelation::disjoint, std::nullopt};
        }
    }
}
auto triangle_area(const Triangle &t) {
    const auto &[A, B, C] = t;
    return det(B - A, C - A) * 0.5;
}
enum class PointShapeRelation : int { inside = -1, on = 0, outside = 1 };
auto point_circle_relation(const Point &P, const Circle &c) {
    const auto &[O, r] = c;
    auto d = (P - O).len();
    return PointShapeRelation(sign(r - d));
}
enum class CircleCircleRelation {
    identital,
    disjoint,
    externally_tangent,
    internally_tangent_1_to_2,
    internally_tangent_2_to_1,
    circle1_contains_circle2,
    circle2_contains_circle1,
    intersecting,
};
auto circie_circle_relation(const Circle &c1, const Circle &c2) {
    using enum CircleCircleRelation;
    const auto &[O1, r1] = c1;
    const auto &[O2, r2] = c2;
    auto d = (O2 - O1).len();
    if (sign(d) == 0 && sign(r1 - r2) == 0) {
        return identital;
    }
    switch (sign(d - r1 - r2)) {
        case 0:
            return externally_tangent;
        case 1:
            return disjoint;
        default:
            switch (sign(d - std::fabs(r1 - r2))) {
                case 0:
                    return r1 > r2 ? internally_tangent_2_to_1 : internally_tangent_1_to_2;
                case -1:
                    return r1 > r2 ? circle1_contains_circle2 : circle2_contains_circle1;
                default:
                    return intersecting;
            }
    }
}
auto circle_circle_intersection(
    const Circle &c1, const Circle &c2
) -> std::pair<CircleCircleRelation, std::variant<std::monostate, Point, std::pair<Point, Point>>> {
    const auto &[O1, r1] = c1;
    const auto &[O2, r2] = c2;
    auto relation = circie_circle_relation(c1, c2);
    auto d = (O2 - O1).len();
    auto d1 = 0.5 * (d + sqr_diff(r1, r2) / d);
    auto H = O1 + d1 * (O2 - O1) / d;
    switch (relation) {
        using enum CircleCircleRelation;
        case disjoint:
        case identital:
        case circle1_contains_circle2:
        case circle2_contains_circle1:
            return {relation, std::monostate()};
        case externally_tangent:
        case internally_tangent_1_to_2:
        case internally_tangent_2_to_1:
            return {relation, H};
        case intersecting: {
            auto v = (O2 - O1).unit().normal() * sqrt(sqr_diff(r1, d1));
            return {relation, std::make_pair(H + v, H - v)};
        }
    }
}
enum class CircleLineRelation { intersecting = -1, tangent = 0, disjoint = 1 };
auto circle_line_relation(const Circle &c, const Line &l) {
    const auto &[O, r] = c;
    auto d = point_line_distance(O, l);
    return CircleLineRelation(sign(r - d));
}
auto circle_line_intersection(const Circle &c, const Line &l)
    -> std::pair<CircleLineRelation, std::variant<std::monostate, Point, std::pair<Point, Point>>> {
    const auto &[O, r] = c;
    const auto &[A, B] = l;
    Point H = projection(O, l);
    auto relation = circle_line_relation(c, l);
    switch (relation) {
        using enum CircleLineRelation;
        case disjoint:
            return {relation, std::monostate()};
        case tangent:
            return {relation, H};
        case intersecting:
            double d = (H - O).len();
            auto v = (A - B).unit() * sqrt(sqr_diff(r, d));
            return {relation, std::make_pair(H + v, H - v)};
    }
}
auto circle_point_tangent(const Circle &c, const Point &P)
    -> std::pair<PointShapeRelation, std::variant<std::monostate, Point, std::pair<Point, Point>>> {
    const auto &[O, r] = c;
    auto relation = point_circle_relation(P, c);
    switch (relation) {
        using enum PointShapeRelation;
        case inside:
            return {relation, std::monostate()};
        case on:
            return {relation, P};
        case outside:
            auto d = (P - O).len();
            auto H = O + (P - O) * (r * r / d);
            auto v = (P - O).unit().normal() * sqrt(sqr_diff(r, d));
            return {relation, std::make_pair(H + v, H - v)};
    }
}
auto circumscribed_circle(const Triangle &t) {
    const auto &[A, B, C] = t;
    auto [relation, O] = line_intersection(
        {middle(A, B), middle(A, B) + (A - B).normal()},
        {middle(B, C), middle(B, C) + (B - C).normal()}
    );
    return relation == LineLineRelation::intersecting
               ? std::optional<Circle>{Circle{O.value(), (O.value() - A).len()}}
               : std::nullopt;
}
auto inscribed_circle(const Triangle &t) {
    const auto &[A, B, C] = t;
    auto a = (B - C).len(), b = (C - A).len(), c = (A - B).len();
    auto I = (A * a + B * b + C * c) / (a + b + c);
    double d = point_line_distance(I, {A, B});
    return sign(d) == 0 ? std::nullopt : std::optional<Circle>{Circle{I, d}};
}
auto external_co_tangent(const Circle &c1, const Circle &c2)
    -> std::variant<std::monostate, Line, std::pair<Line, Line>> {
    const auto &[O1, r1] = c1;
    const auto &[O2, r2] = c2;
    if (r1 < r2) {
        return external_co_tangent(c2, c1);
    }
    const auto &[relation, p] = circle_point_tangent({O1, r1 - r2}, O2);
    switch (relation) {
        using enum PointShapeRelation;
        case inside:
            return std::monostate();
        case on: {
            const auto &P = std::get<1>(p);
            return Line{P, P + (O1 - P).normal()};
        }
        case outside:
            const auto &[P1, P2] = std::get<2>(p);
            auto v1 = (P1 - O1).unit() * r2;
            auto v2 = (P2 - O1).unit() * r2;
            return std::make_pair(Line{P1 + v1, P2 + v2}, Line{O1 + v1, O2 + v2});
    }
}
auto internal_co_tangent(const Circle &c1, const Circle &c2)
    -> std::variant<std::monostate, Line, std::pair<Line, Line>> {
    const auto &[O1, r1] = c1;
    const auto &[O2, r2] = c2;
    if (r1 < r2) {
        return internal_co_tangent(c2, c1);
    }
    const auto &[relation, p] = circle_point_tangent({O1, r1 + r2}, O2);
    switch (relation) {
        using enum PointShapeRelation;
        case inside:
            return std::monostate();
        case on: {
            const auto &P = std::get<1>(p);
            return Line{P, P + (O1 - P).normal()};
        }
        case outside: {
            const auto &[P1, P2] = std::get<2>(p);
            auto v1 = (P1 - O1).unit() * r2;
            auto v2 = (P2 - O1).unit() * r2;
            return {std::make_pair(Line{P1 - v1, O2 + v1}, Line{P2 - v2, O2 + v1})};
        }
    }
}
auto convex_hull(std::vector<Point> points) {
    if (points.size() <= 2) {
        return points;
    }
    int n = (int) points.size();
    std::vector<Point> stk(n + 1);
    std::sort(points.begin(), points.end(), [](const Point &A, const Point &B) {
        return A.x == B.x ? A.y < B.y : A.x < B.x;
    });
    int top = 0;
    stk[top++] = points[0];
    for (int i = 1; i < n; ++i) {
        while (2 <= top && side_of_line(points[i], {stk[top - 2], stk[top - 1]}) != Side::left) {
            --top;
        }
        stk[top++] = points[i];
    }
    int tmp = top;
    for (int i = n - 2; i >= 0; --i) {
        while (tmp < top && side_of_line(points[i], {stk[top - 2], stk[top - 1]}) != Side::left) {
            --top;
        }
        stk[top++] = points[i];
    }
    stk.erase(stk.begin() + top - 1, stk.end());
    stk.shrink_to_fit();
    return stk;
}
auto point_in_convex_polygon(const Point &P, const Polygon &p) {
    using enum PointShapeRelation;
    auto n = p.size();
    if (n < 3) {
        throw std::runtime_error("point_in_convex_polygon: polygon must have at least 3 points");
    }
    if (P.x < p[0].x || (P.x == p[0].x && P.y < p[0].y)) {
        return outside;
    }
    if (side_of_line(P, {p[0], p[1]}) == Side::on) {
        return sign(dot(p[1] - P, p[0] - P)) <= 0 ? on : outside;
    }
    if (side_of_line(P, {p[0], p[n - 1]}) == Side::on) {
        return sign(dot(p[n - 1] - P, p[0] - P)) <= 0 ? on : outside;
    }
    auto i = std::upper_bound(
                 p.begin() + 1,
                 p.end(),
                 P,
                 [&](const Point &A, const Point &B) {
                     return side_of_line(p[0], {A, B}) == Side::left;
                 }
             )
             - p.begin();
    return PointShapeRelation(side_of_line(P, {p[i - 1], p[i]}));
}
auto minkowski_sum(const Polygon &a, const Polygon &b) {
    auto push_point = [](Polygon &v, const Point &P) {
        while (2 <= v.size() && side_of_line(P, {v[v.size() - 2], v.back()}) != Side::left) {
            v.pop_back();
        }
        v.emplace_back(P);
    };
    auto n = a.size(), m = b.size();
    size_t i = 0, j = 0;
    Polygon c;
    c.reserve(n + m);
    push_point(c, a.front() + b.front());
    while (i < n && j < m) {
        auto u = a[(i + 1) % n] - a[i];
        auto v = b[(j + 1) % m] - b[j];
        if (0 < det(u, v)) {
            push_point(c, c.back() + u);
            ++i;
        } else {
            push_point(c, c.back() + v);
            ++j;
        }
    }
    for (; i < n; ++i) {
        push_point(c, c.back() + a[(i + 1) % n] - a[i]);
    }
    for (; j < m; ++j) {
        push_point(c, c.back() + b[(j + 1) % m] - b[j]);
    }
    push_point(c, c.front());
    c.pop_back();
    return c;
}
auto point_in_polygon(const Point &P, const Polygon &p) {
    using enum PointShapeRelation;
    bool result = false;
    for (size_t i = 0, n = p.size(); i < n; ++i) {
        auto A = p[i];
        auto B = p[(i + 1) % n];
        if (point_on_segment(P, {A, B})) {
            return on;
        }
        if (A.y > B.y) {
            std::swap(A, B);
        }
        if (sign(A.y - P.y) <= 0 && sign(P.y - B.y) < 0 && side_of_line(P, {A, B}) == Side::left) {
            result ^= 1;
        }
    }
    return result ? inside : outside;
}
auto polygon_area(const Polygon &p) {
    double result = 0;
    for (size_t i = 0, n = p.size(); i < n; ++i) {
        result += triangle_area({p[0], p[i], p[(i + 1) % n]});
    }
    return result;
}
auto half_planes_intersection(std::vector<Line> lines) {
    using enum Side;
    if (lines.empty()) {
        throw std::runtime_error("half_planes_intersection: lines must not be empty");
    }
    std::deque<Line> q;
    std::deque<Point> t;
    std::sort(lines.begin(), lines.end(), [](const auto &l1, const auto &l2) {
        int d = sign((l1.second - l1.first).angle() - (l2.second - l2.first).angle());
        return d == 0 ? side_of_line(l1.first, l2) == left : d < 0;
    });
    q.emplace_back(lines[0]);
    for (const auto &line: lines) {
        if (parallel(q.back(), line)) {
            continue;
        }
        while (!t.empty() && side_of_line(t.back(), line) != left) {
            t.pop_back();
            q.pop_back();
        }
        while (!t.empty() && side_of_line(t.front(), line) != left) {
            t.pop_front();
            q.pop_front();
        }
        q.emplace_back(line);
        t.emplace_back(line_intersection(q.back(), line).second.value());
    }
    while (!t.empty() && side_of_line(t.back(), q.front()) != left) {
        t.pop_back();
        q.pop_back();
    }
    if (q.size() > 1) {
        t.emplace_front(line_intersection(q.front(), q.back()).second.value());
    }
    return std::pair{std::vector{q.begin(), q.end()}, Polygon{t.begin(), t.end()}};
}
auto polygons_union_area(const std::span<Polygon> &polygons) {
    auto n = polygons.size();
    std::vector<Line> lines;
    for (size_t i = 0; i < n; ++i) {
        for (size_t m = polygons[i].size(), j = 0; j < m; ++j) {
            lines.emplace_back(polygons[i][j], polygons[i][(j + 1) % m]);
        }
    }
    auto m = lines.size();
    std::vector<size_t> fa(m);
    std::vector<std::vector<std::tuple<size_t, Point, Side, Side>>> events(m);
    std::iota(fa.begin(), fa.end(), 0);
    std::function<size_t(size_t)> find;
    find = [&](size_t x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    };
    for (size_t i = 0; i < m; ++i) {
        for (size_t j = i + 1; j < m; ++j) {
            if (auto u = find(i), v = find(j); u != v) {
                if (auto [relation, _] = line_intersection(lines[i], lines[j]);
                    relation == LineLineRelation::identical) {
                    fa[u] = v;
                }
            }
        }
    }
    for (size_t i = 0; i < m; ++i) {
        for (size_t j = i + 1; j < m; ++j) {
            if (auto u = find(i), v = find(j); u != v) {
                if (auto [relation, I] = line_intersection(lines[u], lines[v]);
                    relation == LineLineRelation::intersecting) {
                    const auto &[A, B] = lines[i];
                    const auto &[C, D] = lines[j];
                    auto sideA = side_of_line(A, {C, D});
                    auto sideB = side_of_line(B, {C, D});
                    auto sideC = side_of_line(C, {A, B});
                    auto sideD = side_of_line(D, {A, B});
                    if (sideA != sideB) {
                        events[find(j)].emplace_back(i, I.value(), sideA, sideB);
                    }
                    if (sideC != sideD) {
                        events[find(i)].emplace_back(j, I.value(), sideC, sideD);
                    }
                }
            }
        }
    }
    double res = 0;
    for (size_t i = 0; i < m; ++i) {
        if (find(i) != i) {
            continue;
        }
        const auto &[a, b] = lines[i];
        std::sort(events[i].begin(), events[i].end(), [&](const auto &a, const auto &b) {
            return std::get<0>(a) < std::get<0>(b);
        });
        events[i].erase(
            std::unique(
                events[i].begin(),
                events[i].end(),
                [&](const auto &a, const auto &b) { return std::get<0>(a) == std::get<0>(b); }
            ),
            events[i].end()
        );
        events[i].erase(
            std::remove_if(
                events[i].begin(),
                events[i].end(),
                [&](const auto &a) { return find(std::get<0>(a)) == i; }
            ),
            events[i].end()
        );
        std::sort(events[i].begin(), events[i].end(), [a, b](const auto &p, const auto &q) {
            return dot(std::get<1>(p) - a, b - a) < dot(std::get<1>(q) - a, b - a);
        });
        int cntl = 0, cntr = 0;
        double last;
        auto unit = (b - a).unit();
        for (auto const &[id, o, sideC, sideD]: events[i]) {
            auto dis = dot(o - a, unit);
            if (cntl != 0 && cntr == 0) {
                res += det(a + unit * last, a + unit * dis);
            }
            if (sideC == Side::left) {
                ++cntl;
            }
            if (sideD == Side::left) {
                --cntl;
            }
            if (sideC == Side::right) {
                --cntr;
            }
            if (sideD == Side::right) {
                ++cntr;
            }
            last = dis;
        }
    }
    return res / 2;
}

auto diameter(const Polygon &p) {
    int n = (int) p.size();
    if (n == 1) {
        return 0.0;
    }
    if (n == 2) {
        return (p[0] - p[1]).len();
    }
    double ret = 0;
    for (int i = 0, j = i + 1; i < n; ++i) {
        while (det(p[j] - p[i], p[j] - p[(i + 1) % n])
               <= det(p[(j + 1) % n] - p[i], p[(j + 1) % n] - p[(i + 1) % n])) {
            j = (j + 1) % n;
        }
        ret = std::max(ret, (p[j] - p[i]).len2());
        ret = std::max(ret, (p[j] - p[(i + 1) % n]).len2());
    }
    return sqrt(ret);
}

int main() {
    int n;
    scanf("%d", &n);
    Polygon polygons(n);
    for (int i = 0; i < n; ++i) {
        scanf("%lf%lf", &polygons[i].x, &polygons[i].y);
    }
    polygons = convex_hull(polygons);
    /*fprintf(stderr, "%d\n", (int) polygons.size());*/
    printf("%.10lf\n", diameter(polygons));

    return 0;
}

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

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 3948kb

input:

1000
0 0
-997615 -8573
-1988394 -28911
-2726572 -44296
-3491635 -60392
-4419752 -82814
-5298550 -105946
-5723430 -118453
-6608257 -147267
-7034966 -161982
-7563964 -181682
-8507871 -222865
-9499799 -271846
-10090186 -303547
-10400262 -322989
-10614073 -339725
-11081438 -378596
-11791568 -439127
-127...

output:

274339223.1895614266

result:

ok found '274339223.1895614', expected '274339223.1895614', error '0.0000000'

Test #2:

score: 10
Accepted
time: 1ms
memory: 3904kb

input:

1000
0 0
-887614 -1937
-1459359 -3808
-2421409 -24096
-3273181 -48456
-3917594 -76664
-4402753 -100164
-5375022 -150897
-5993935 -192089
-6587159 -238825
-7549680 -333298
-8330993 -416479
-9244392 -515027
-10010900 -598589
-10374584 -640275
-10767641 -686907
-11173081 -741316
-11821952 -833327
-1260...

output:

262687047.9274906218

result:

ok found '262687047.9274906', expected '262687047.9274906', error '0.0000000'

Test #3:

score: 10
Accepted
time: 1ms
memory: 3940kb

input:

1000
0 0
-631055 -2758
-1328409 -7463
-2248672 -20536
-2412978 -23564
-2659543 -28441
-3383179 -43406
-4183375 -64326
-4856658 -88337
-5799682 -134822
-6757348 -189404
-7132846 -212164
-7563226 -242116
-8368716 -300012
-9321463 -381770
-9831821 -432746
-10409503 -491057
-11360852 -607259
-11874199 -...

output:

257868038.6435896754

result:

ok found '257868038.6435897', expected '257868038.6435897', error '0.0000000'

Test #4:

score: 10
Accepted
time: 1ms
memory: 3904kb

input:

1000
0 0
-48652 -588
-951356 -20091
-1517426 -33325
-1965414 -51971
-2466111 -74904
-3046762 -103888
-3555833 -132002
-3976901 -156059
-4972848 -245498
-5921476 -332492
-6353035 -375491
-7327511 -496188
-7939064 -575429
-8842272 -694656
-9246222 -756797
-9771758 -860630
-10633761 -1031205
-10981774 ...

output:

259539672.4804533720

result:

ok found '259539672.4804534', expected '259539672.4804534', error '0.0000000'

Test #5:

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

input:

1000
0 0
-456569 -2668
-1141521 -7887
-1270801 -8967
-1971135 -21206
-2919889 -38188
-3903859 -71231
-4752603 -107450
-5508682 -143873
-6214620 -183392
-6718977 -212193
-7452291 -271600
-8408796 -354998
-9261882 -432674
-9528618 -457608
-10099091 -513153
-10320120 -535958
-11067358 -614356
-12050731...

output:

250217366.4826218486

result:

ok found '250217366.4826218', expected '250217366.4826218', error '0.0000000'

Test #6:

score: 10
Accepted
time: 1ms
memory: 3952kb

input:

1000
0 0
-794019 -17307
-1389128 -41522
-1928884 -68000
-2530256 -103641
-3335109 -158872
-4273633 -225636
-4655012 -253747
-5584931 -329387
-6190262 -382029
-6657521 -422826
-7445510 -497270
-8092482 -562235
-8879759 -646264
-9688106 -745847
-10545954 -857573
-11350736 -962711
-12106702 -1066386
-1...

output:

256130723.0053679943

result:

ok found '256130723.0053680', expected '256130723.0053680', error '0.0000000'

Test #7:

score: 10
Accepted
time: 1ms
memory: 4148kb

input:

1000
0 0
-785524 -1241
-1228373 -2123
-1584480 -5108
-2516949 -19826
-3109735 -51256
-3799285 -95138
-4215892 -125263
-5144743 -202941
-6071171 -287679
-6844072 -376760
-7786583 -487933
-8491316 -575443
-9458832 -700691
-9848966 -756816
-10135682 -798578
-11100151 -940696
-11527785 -1004652
-1221960...

output:

268992022.0570692420

result:

ok found '268992022.0570692', expected '268992022.0570692', error '0.0000000'

Test #8:

score: 10
Accepted
time: 1ms
memory: 3988kb

input:

1000
0 0
-787651 -697
-1319793 -8691
-1545057 -12462
-2239671 -24650
-2487763 -36810
-2983386 -61694
-3408212 -85910
-3650815 -105325
-4268088 -155258
-5088483 -225550
-5720403 -280762
-6036913 -309102
-6663280 -365291
-7656626 -456948
-8462737 -538137
-9318271 -628471
-9704990 -671367
-10363047 -74...

output:

251395356.7229873240

result:

ok found '251395356.7229873', expected '251395356.7229873', error '0.0000000'

Test #9:

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

input:

1000
0 0
-895815 -18037
-1536713 -40507
-2439825 -73040
-2896761 -94230
-3815334 -138606
-4520738 -176711
-4997585 -208924
-5399492 -237632
-5629592 -254751
-6518310 -320902
-7084766 -367663
-7724052 -423029
-8475256 -492590
-9071702 -551527
-9798581 -626155
-10535448 -702512
-11155572 -768931
-1208...

output:

259639018.6166957319

result:

ok found '259639018.6166957', expected '259639018.6166958', error '0.0000000'

Test #10:

score: 10
Accepted
time: 1ms
memory: 3952kb

input:

1000
0 0
-837332 -2192
-1593910 -10845
-2320576 -25425
-3294539 -45660
-4178010 -82673
-4936159 -128518
-5796274 -190640
-6313517 -228540
-7131129 -291797
-7751205 -354513
-8357330 -419926
-9355375 -542247
-9783911 -596434
-10313681 -667126
-10377189 -675659
-10824619 -750345
-11653618 -894218
-1234...

output:

267554454.1762451231

result:

ok found '267554454.1762451', expected '267554454.1762451', error '0.0000000'

Test #11:

score: 10
Accepted
time: 1ms
memory: 3892kb

input:

1000
0 0
-758133 -3909
-1146524 -7212
-1823781 -16200
-2561994 -26923
-3448934 -43815
-4337557 -80953
-4912706 -106752
-5770093 -182352
-6645519 -261073
-7156648 -309532
-7882740 -380211
-8731241 -470527
-9265139 -532092
-10083113 -633235
-10767248 -721935
-11729364 -862416
-12112647 -921658
-128310...

output:

259903024.7335910201

result:

ok found '259903024.7335910', expected '259903024.7335910', error '0.0000000'

Test #12:

score: 10
Accepted
time: 1ms
memory: 4004kb

input:

1000
0 0
-220082 -1509
-1148190 -9207
-2108923 -22196
-2713299 -30623
-3364648 -43866
-3891571 -54675
-4300261 -63335
-4622311 -72814
-5235380 -91992
-5680720 -106355
-6138401 -121807
-7013302 -160828
-7784753 -195568
-8750494 -245022
-9681201 -295430
-10320328 -334255
-11256371 -407963
-12199734 -4...

output:

261658565.5826949477

result:

ok found '261658565.5826949', expected '261658565.5826949', error '0.0000000'

Test #13:

score: 10
Accepted
time: 1ms
memory: 3944kb

input:

1000
0 0
-425515 -4558
-1293469 -14675
-1990220 -30271
-2703160 -49015
-3455818 -76450
-4210140 -107243
-4530367 -120805
-5136478 -158180
-5732363 -196472
-6247394 -230823
-7100635 -290064
-7703961 -335663
-8091361 -368200
-8752153 -427341
-9433796 -491521
-10139006 -563945
-10984402 -653149
-113386...

output:

256353710.9730163217

result:

ok found '256353710.9730163', expected '256353710.9730163', error '0.0000000'

Test #14:

score: 10
Accepted
time: 0ms
memory: 3896kb

input:

1000
0 0
-572806 -2255
-1477072 -15611
-1643871 -18681
-2578790 -51107
-3303402 -86192
-4032032 -123256
-4540711 -150307
-5462171 -206756
-6377222 -264514
-6921545 -316752
-7623842 -390821
-8329739 -466169
-9034451 -568935
-9600887 -653814
-9729771 -674650
-10461476 -795876
-11348904 -952387
-117122...

output:

255498134.5157807171

result:

ok found '255498134.5157807', expected '255498134.5157807', error '0.0000000'

Test #15:

score: 10
Accepted
time: 1ms
memory: 3904kb

input:

1000
0 0
-723350 -3997
-1405147 -10223
-2296494 -21394
-2876280 -32357
-3572827 -51397
-4452032 -87137
-4953249 -111910
-5388609 -141252
-5731586 -165403
-6101332 -197003
-6884756 -282055
-7719066 -372715
-8101214 -415308
-8855617 -516206
-9316024 -579909
-10091662 -705732
-10621099 -799022
-1137369...

output:

258992362.5300114155

result:

ok found '258992362.5300114', expected '258992362.5300114', error '0.0000000'

Test #16:

score: 10
Accepted
time: 1ms
memory: 3948kb

input:

1000
0 0
-638945 -769
-1345094 -2633
-2049372 -9786
-3043001 -20660
-3832821 -40968
-4616354 -61996
-5489016 -89554
-6075577 -112116
-7059918 -153506
-7917375 -193461
-8704241 -235730
-9411173 -289585
-9928254 -332456
-10816688 -407937
-11522358 -469782
-12333778 -541183
-12532282 -560003
-13293480 ...

output:

260884926.0498460531

result:

ok found '260884926.0498461', expected '260884926.0498461', error '0.0000000'

Test #17:

score: 10
Accepted
time: 1ms
memory: 3948kb

input:

1000
0 0
-929784 -9273
-1222089 -14360
-1633168 -22589
-2271669 -42262
-2863939 -61639
-3538074 -85549
-4537727 -127500
-5529674 -172462
-6106076 -217405
-6615381 -262810
-7383575 -342936
-8289266 -445052
-8474592 -467243
-9285779 -564519
-10059545 -662251
-10774681 -753541
-11666601 -869701
-120587...

output:

259788149.3996045291

result:

ok found '259788149.3996045', expected '259788149.3996045', error '0.0000000'

Test #18:

score: 10
Accepted
time: 1ms
memory: 3948kb

input:

1000
0 0
-436597 -2249
-897574 -4839
-1763026 -9858
-2199595 -14239
-2837069 -24431
-3656371 -67025
-4153771 -93216
-5062244 -151716
-5634320 -190859
-6503474 -278174
-7250273 -366225
-7276046 -369834
-7806600 -448708
-8317734 -530915
-8905662 -634997
-9766507 -790590
-9973653 -831916
-10555366 -955...

output:

277834510.7780300379

result:

ok found '277834510.7780300', expected '277834510.7780300', error '0.0000000'

Test #19:

score: 10
Accepted
time: 1ms
memory: 3924kb

input:

1000
0 0
-499456 -5028
-1395210 -19193
-2095999 -36599
-2278240 -43145
-2754419 -63055
-3701264 -104359
-4078225 -133214
-4292562 -151446
-5087031 -220375
-5649235 -277762
-6403916 -358749
-7403700 -470022
-7940233 -537110
-8433330 -607694
-9376563 -746831
-9903004 -831307
-10718505 -965214
-1171369...

output:

261984352.6271107793

result:

ok found '261984352.6271108', expected '261984352.6271108', error '0.0000000'

Test #20:

score: 10
Accepted
time: 1ms
memory: 3992kb

input:

1000
0 0
-347123 -2330
-1296972 -12856
-2114794 -28811
-3005647 -54768
-3802579 -79440
-4777546 -118441
-5386348 -146049
-6230831 -184743
-7083665 -250364
-7963538 -324047
-8621014 -381656
-9065618 -421654
-9883960 -496406
-10349110 -541972
-11146897 -621572
-12108943 -718091
-12921588 -803916
-1348...

output:

265979549.5809911788

result:

ok found '265979549.5809912', expected '265979549.5809912', error '0.0000000'

Subtask #2:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #21:

score: 30
Accepted
time: 9ms
memory: 5168kb

input:

30000
0 0
-27842 -9
-56782 -24
-64412 -29
-91618 -47
-121087 -68
-152541 -123
-182316 -183
-212916 -274
-234159 -341
-266126 -446
-289328 -523
-317883 -637
-340594 -728
-350940 -781
-374263 -905
-400736 -1046
-427862 -1199
-450458 -1327
-465289 -1413
-485809 -1534
-517032 -1724
-548368 -1921
-576015...

output:

254843548.6986402571

result:

ok found '254843548.6986403', expected '254843548.6986403', error '0.0000000'

Test #22:

score: 30
Accepted
time: 9ms
memory: 5160kb

input:

30000
0 0
-31209 -21
-39334 -27
-64601 -46
-86568 -64
-115119 -89
-143398 -117
-161108 -154
-179520 -196
-203131 -254
-234209 -335
-252923 -396
-275417 -473
-289767 -533
-311588 -627
-343100 -821
-369994 -998
-385492 -1101
-412257 -1281
-427669 -1387
-453860 -1575
-485750 -1817
-510891 -2019
-531160...

output:

250853956.0239689052

result:

ok found '250853956.0239689', expected '250853956.0239689', error '0.0000000'

Test #23:

score: 30
Accepted
time: 9ms
memory: 5184kb

input:

30000
0 0
-20075 -15
-53286 -46
-77410 -74
-104765 -117
-128452 -158
-138117 -176
-145933 -192
-169668 -264
-195119 -349
-220533 -437
-227177 -463
-259461 -594
-288461 -712
-304625 -788
-337671 -947
-358291 -1056
-388248 -1227
-411605 -1362
-422810 -1433
-444967 -1583
-464234 -1714
-471059 -1763
-48...

output:

250990461.7585058212

result:

ok found '250990461.7585058', expected '250990461.7585058', error '0.0000000'

Test #24:

score: 30
Accepted
time: 4ms
memory: 5100kb

input:

30000
0 0
-25406 -9
-53669 -24
-62096 -33
-84905 -59
-97980 -83
-118490 -127
-139980 -180
-168464 -256
-187325 -315
-208655 -393
-215588 -421
-244663 -541
-261958 -614
-288250 -735
-294235 -765
-308563 -838
-338619 -993
-350477 -1059
-363699 -1134
-379676 -1232
-398726 -1354
-430095 -1576
-459666 -1...

output:

253698546.2001740336

result:

ok found '253698546.2001740', expected '253698546.2001740', error '0.0000000'

Test #25:

score: 30
Accepted
time: 4ms
memory: 5160kb

input:

30000
0 0
-21134 -9
-45635 -23
-62583 -36
-90936 -72
-123048 -113
-148384 -151
-173729 -190
-194644 -225
-207752 -258
-236495 -342
-241543 -359
-272810 -476
-303141 -602
-324057 -690
-344614 -778
-364773 -871
-380490 -948
-407975 -1083
-433651 -1212
-464879 -1383
-485067 -1502
-513615 -1674
-537857 ...

output:

249331713.2810479105

result:

ok found '249331713.2810479', expected '249331713.2810479', error '0.0000000'

Test #26:

score: 30
Accepted
time: 9ms
memory: 5188kb

input:

30000
0 0
-21448 -2
-26656 -6
-55814 -36
-82967 -67
-107428 -97
-134427 -133
-152614 -158
-171092 -185
-199260 -236
-221094 -282
-254022 -354
-285389 -431
-318637 -513
-346959 -588
-371288 -663
-398215 -753
-430925 -909
-460659 -1052
-492385 -1212
-522834 -1369
-544343 -1480
-574493 -1645
-591923 -1...

output:

252099986.1016024053

result:

ok found '252099986.1016024', expected '252099986.1016024', error '0.0000000'

Test #27:

score: 30
Accepted
time: 9ms
memory: 5172kb

input:

30000
0 0
-14622 -3
-21004 -5
-52082 -23
-74883 -43
-96336 -71
-128458 -113
-156799 -154
-183046 -195
-192091 -210
-222978 -268
-242938 -309
-262594 -352
-278459 -388
-305011 -451
-334920 -535
-359764 -614
-386317 -705
-387178 -708
-403823 -768
-433061 -876
-462803 -990
-476883 -1056
-501388 -1177
-...

output:

252058372.1872791648

result:

ok found '252058372.1872792', expected '252058372.1872792', error '0.0000000'

Test #28:

score: 30
Accepted
time: 9ms
memory: 5200kb

input:

30000
0 0
-25620 -6
-58948 -27
-81188 -42
-108084 -65
-116725 -73
-125232 -81
-135235 -91
-151536 -109
-184450 -152
-207622 -186
-226702 -226
-253157 -296
-272563 -363
-285333 -416
-314647 -544
-343300 -671
-374313 -814
-396287 -921
-420576 -1040
-429098 -1083
-461737 -1259
-484471 -1384
-514561 -15...

output:

250472754.0190104544

result:

ok found '250472754.0190105', expected '250472754.0190105', error '0.0000000'

Test #29:

score: 30
Accepted
time: 6ms
memory: 5072kb

input:

30000
0 0
-33296 -14
-53478 -25
-77571 -40
-102204 -60
-131127 -87
-154300 -115
-164094 -129
-170807 -139
-182721 -162
-204059 -213
-233651 -291
-248862 -344
-272501 -427
-292422 -497
-316393 -587
-332926 -655
-357527 -758
-377377 -846
-400755 -952
-421907 -1051
-432483 -1106
-463837 -1277
-484678 -...

output:

250911365.3928250968

result:

ok found '250911365.3928251', expected '250911365.3928251', error '0.0000000'

Test #30:

score: 30
Accepted
time: 6ms
memory: 5240kb

input:

30000
0 0
-16184 -12
-47000 -41
-65809 -62
-97992 -98
-130432 -136
-141298 -155
-166593 -204
-199502 -297
-227146 -379
-253391 -469
-268774 -523
-296503 -636
-323982 -757
-356038 -900
-373220 -977
-398856 -1098
-425367 -1243
-452654 -1396
-476703 -1537
-489569 -1615
-493812 -1641
-521509 -1812
-5419...

output:

250844611.9027090669

result:

ok found '250844611.9027091', expected '250844611.9027091', error '0.0000000'

Test #31:

score: 30
Accepted
time: 9ms
memory: 5256kb

input:

30000
0 0
-25799 -4
-55851 -26
-80970 -45
-101274 -62
-132285 -92
-156585 -119
-172335 -137
-194967 -166
-207127 -182
-210322 -187
-232931 -224
-254065 -285
-276296 -355
-296092 -422
-319568 -506
-341162 -585
-366961 -682
-378425 -726
-406880 -836
-433997 -944
-462505 -1063
-484234 -1155
-510379 -12...

output:

252561817.9649026096

result:

ok found '252561817.9649026', expected '252561817.9649026', error '0.0000000'

Test #32:

score: 30
Accepted
time: 9ms
memory: 5112kb

input:

30000
0 0
-26056 -4
-54769 -14
-60303 -16
-87623 -57
-116864 -112
-138854 -159
-157862 -208
-175152 -264
-200884 -367
-230497 -499
-252728 -608
-270362 -698
-296046 -842
-305774 -898
-310136 -925
-332152 -1067
-333986 -1079
-355425 -1222
-364727 -1286
-382658 -1414
-392920 -1492
-425026 -1737
-44041...

output:

253995087.9124097824

result:

ok found '253995087.9124098', expected '253995087.9124098', error '0.0000000'

Test #33:

score: 30
Accepted
time: 9ms
memory: 5072kb

input:

30000
0 0
-9535 -2
-40752 -11
-60579 -26
-93471 -57
-118567 -94
-144069 -132
-173022 -182
-195295 -224
-223889 -296
-247193 -355
-264085 -399
-290833 -470
-296735 -486
-316658 -542
-335761 -609
-366899 -722
-382069 -779
-411737 -894
-434702 -985
-457466 -1078
-487157 -1201
-497974 -1248
-524864 -136...

output:

252472448.5275533199

result:

ok found '252472448.5275533', expected '252472448.5275533', error '0.0000000'

Test #34:

score: 30
Accepted
time: 4ms
memory: 5188kb

input:

30000
0 0
-24944 -5
-45218 -18
-63052 -30
-95222 -53
-122297 -76
-142451 -95
-166142 -128
-198625 -176
-224888 -226
-256971 -297
-268524 -323
-295294 -399
-316093 -462
-346071 -556
-357361 -596
-384063 -695
-413239 -808
-431516 -883
-455899 -988
-477258 -1083
-482936 -1109
-514885 -1259
-545203 -140...

output:

251091289.9211815596

result:

ok found '251091289.9211816', expected '251091289.9211816', error '0.0000000'

Test #35:

score: 30
Accepted
time: 6ms
memory: 5236kb

input:

30000
0 0
-30995 -2
-54625 -11
-82116 -24
-107137 -37
-118814 -46
-145376 -68
-153252 -80
-185690 -144
-216437 -215
-233722 -272
-253995 -343
-271631 -413
-292398 -507
-321561 -641
-349834 -782
-373847 -909
-394268 -1020
-413992 -1130
-437644 -1265
-455088 -1371
-479307 -1520
-487919 -1573
-510069 -...

output:

252314719.9735080898

result:

ok found '252314719.9735081', expected '252314719.9735081', error '0.0000000'

Test #36:

score: 30
Accepted
time: 4ms
memory: 5156kb

input:

30000
0 0
-27620 -15
-32869 -18
-63930 -40
-92226 -71
-117410 -103
-128286 -121
-160858 -177
-175636 -204
-202913 -255
-210245 -270
-231489 -321
-239502 -341
-270542 -438
-300109 -534
-328778 -641
-347216 -724
-378021 -873
-405203 -1017
-433216 -1174
-466343 -1375
-485498 -1495
-512206 -1683
-537113...

output:

252132224.5177777708

result:

ok found '252132224.5177778', expected '252132224.5177778', error '0.0000000'

Test #37:

score: 30
Accepted
time: 9ms
memory: 5084kb

input:

30000
0 0
-26512 -10
-51854 -27
-59926 -34
-72478 -45
-104402 -85
-134454 -126
-156279 -156
-187348 -202
-204100 -236
-236516 -302
-257885 -347
-283292 -401
-304536 -460
-329866 -533
-362401 -630
-368232 -649
-393217 -739
-412750 -810
-443034 -922
-470338 -1029
-481188 -1073
-497958 -1151
-530836 -1...

output:

251728991.7551814914

result:

ok found '251728991.7551815', expected '251728991.7551815', error '0.0000000'

Test #38:

score: 30
Accepted
time: 8ms
memory: 5244kb

input:

30000
0 0
-29212 -4
-38598 -7
-71599 -25
-95384 -48
-122534 -75
-152884 -108
-185395 -148
-193339 -166
-211296 -218
-242492 -319
-262879 -390
-280381 -452
-297193 -522
-316047 -608
-344702 -748
-362716 -837
-371851 -884
-392232 -990
-415911 -1120
-428530 -1190
-455344 -1346
-476289 -1469
-502141 -16...

output:

252836476.4363638759

result:

ok found '252836476.4363639', expected '252836476.4363639', error '0.0000000'

Test #39:

score: 30
Accepted
time: 8ms
memory: 5088kb

input:

30000
0 0
-32998 -8
-60868 -23
-90627 -40
-119903 -65
-145529 -87
-161760 -103
-169947 -115
-194965 -153
-217424 -191
-240218 -232
-262746 -278
-274663 -306
-300259 -367
-311698 -396
-338898 -472
-371940 -583
-391272 -648
-422137 -773
-450678 -889
-472143 -979
-498399 -1098
-530708 -1249
-553762 -13...

output:

254810274.4235500395

result:

ok found '254810274.4235500', expected '254810274.4235500', error '0.0000000'

Test #40:

score: 30
Accepted
time: 8ms
memory: 5080kb

input:

30000
0 0
-8940 -5
-33085 -27
-59867 -53
-86492 -79
-109768 -109
-130705 -139
-137599 -149
-167036 -193
-175992 -209
-205088 -262
-231732 -316
-253027 -361
-277001 -412
-306909 -477
-319514 -507
-337756 -557
-357495 -615
-372846 -661
-389281 -720
-409556 -800
-431984 -897
-439453 -931
-470069 -1095
...

output:

252714495.2776288390

result:

ok found '252714495.2776288', expected '252714495.2776289', error '0.0000000'

Subtask #3:

score: 60
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #41:

score: 60
Accepted
time: 144ms
memory: 34008kb

input:

500000
0 0
-1984 -1
-3948 -2
-5906 -3
-7858 -4
-9782 -5
-11687 -6
-13584 -7
-15396 -8
-17164 -9
-18920 -10
-20662 -11
-22403 -12
-24141 -13
-25841 -14
-27533 -15
-29130 -16
-30717 -17
-32294 -18
-33869 -19
-35416 -20
-36958 -21
-38470 -22
-39949 -23
-41422 -24
-42890 -25
-44343 -26
-45731 -27
-47089...

output:

250546651.9010666609

result:

ok found '250546651.9010667', expected '250546651.9010667', error '0.0000000'

Test #42:

score: 60
Accepted
time: 131ms
memory: 33904kb

input:

500000
0 0
-1966 -1
-3887 -2
-5788 -3
-7676 -4
-9407 -5
-11076 -6
-12731 -7
-14285 -8
-15829 -9
-17361 -10
-18869 -11
-20358 -12
-21841 -13
-23323 -14
-24788 -15
-26134 -16
-27457 -17
-28627 -18
-29768 -19
-30831 -20
-31881 -21
-32923 -22
-33956 -23
-34977 -24
-36961 -26
-37931 -27
-39798 -29
-40731...

output:

250435395.8838684261

result:

ok found '250435395.8838684', expected '250435395.8838684', error '0.0000000'

Test #43:

score: 60
Accepted
time: 144ms
memory: 34008kb

input:

500000
0 0
-1951 -1
-3898 -2
-5828 -3
-7755 -4
-9668 -5
-11540 -6
-13405 -7
-15238 -8
-17036 -9
-18696 -10
-20310 -11
-21918 -12
-23504 -13
-25087 -14
-26643 -15
-28191 -16
-29738 -17
-31216 -18
-32637 -19
-34040 -20
-35437 -21
-36800 -22
-38134 -23
-39411 -24
-40685 -25
-41952 -26
-43163 -27
-44372...

output:

250864379.7991594076

result:

ok found '250864379.7991594', expected '250864379.7991594', error '0.0000000'

Test #44:

score: 60
Accepted
time: 139ms
memory: 34000kb

input:

500000
0 0
-1966 -1
-3814 -2
-5658 -3
-7499 -4
-9288 -5
-10993 -6
-12683 -7
-14368 -8
-16001 -9
-17554 -10
-19098 -11
-20624 -12
-22046 -13
-23375 -14
-24684 -15
-25923 -16
-27157 -17
-28373 -18
-29570 -19
-30755 -20
-31940 -21
-33061 -22
-34101 -23
-36091 -25
-37085 -26
-39050 -28
-41010 -30
-42924...

output:

250490528.3016454279

result:

ok found '250490528.3016454', expected '250490528.3016454', error '0.0000000'

Test #45:

score: 60
Accepted
time: 141ms
memory: 33892kb

input:

500000
0 0
-2000 -1
-3991 -2
-5959 -3
-7812 -4
-9659 -5
-11486 -6
-13244 -7
-14965 -8
-16685 -9
-18403 -10
-20112 -11
-21769 -12
-23425 -13
-25049 -14
-26661 -15
-28245 -16
-29805 -17
-31321 -18
-32778 -19
-34227 -20
-35648 -21
-37063 -22
-38451 -23
-39834 -24
-41189 -25
-42537 -26
-43862 -27
-45146...

output:

250484765.8163518906

result:

ok found '250484765.8163519', expected '250484765.8163519', error '0.0000000'

Test #46:

score: 60
Accepted
time: 137ms
memory: 33868kb

input:

500000
0 0
-1999 -1
-3969 -2
-5883 -3
-7768 -4
-9646 -5
-11522 -6
-13386 -7
-15249 -8
-17083 -9
-18886 -10
-20620 -11
-22334 -12
-24010 -13
-25682 -14
-27345 -15
-28999 -16
-30653 -17
-32305 -18
-33880 -19
-35447 -20
-36987 -21
-38504 -22
-39992 -23
-41471 -24
-42894 -25
-44296 -26
-45677 -27
-47055...

output:

250230916.1903697848

result:

ok found '250230916.1903698', expected '250230916.1903698', error '0.0000000'

Test #47:

score: 60
Accepted
time: 143ms
memory: 33992kb

input:

500000
0 0
-1957 -1
-3908 -2
-5811 -3
-7704 -4
-9571 -5
-11424 -6
-13257 -7
-15084 -8
-16829 -9
-18554 -10
-20227 -11
-21839 -12
-23449 -13
-25057 -14
-26543 -15
-28022 -16
-29490 -17
-30930 -18
-32353 -19
-33776 -20
-35142 -21
-36453 -22
-37757 -23
-39042 -24
-40309 -25
-41564 -26
-42760 -27
-43906...

output:

251523690.4624040425

result:

ok found '251523690.4624040', expected '251523690.4624040', error '0.0000000'

Test #48:

score: 60
Accepted
time: 143ms
memory: 33912kb

input:

500000
0 0
-1955 -1
-3908 -2
-5832 -3
-7723 -4
-9572 -5
-11411 -6
-13149 -7
-14815 -8
-16416 -9
-18007 -10
-19594 -11
-21168 -12
-22677 -13
-24178 -14
-25679 -15
-27176 -16
-28658 -17
-30129 -18
-31590 -19
-33032 -20
-34442 -21
-35816 -22
-37044 -23
-38207 -24
-39344 -25
-40420 -26
-41421 -27
-43334...

output:

251183725.5046660304

result:

ok found '251183725.5046660', expected '251183725.5046660', error '0.0000000'

Test #49:

score: 60
Accepted
time: 136ms
memory: 33888kb

input:

500000
0 0
-1997 -1
-3931 -2
-5858 -3
-7761 -4
-9578 -5
-11389 -6
-13134 -7
-14876 -8
-16612 -9
-18328 -10
-19994 -11
-21530 -12
-23041 -13
-24493 -14
-25929 -15
-27352 -16
-28721 -17
-30062 -18
-31354 -19
-32639 -20
-33919 -21
-35198 -22
-36458 -23
-37669 -24
-38874 -25
-40072 -26
-41248 -27
-42388...

output:

250578576.6313597560

result:

ok found '250578576.6313598', expected '250578576.6313598', error '0.0000000'

Test #50:

score: 60
Accepted
time: 132ms
memory: 33892kb

input:

500000
0 0
-1945 -1
-3846 -2
-5639 -3
-7414 -4
-9185 -5
-10917 -6
-12609 -7
-14296 -8
-15973 -9
-17613 -10
-19227 -11
-20729 -12
-22204 -13
-23675 -14
-25145 -15
-26563 -16
-27980 -17
-29273 -18
-30544 -19
-31789 -20
-33034 -21
-34257 -22
-35442 -23
-36592 -24
-37740 -25
-38877 -26
-39955 -27
-41029...

output:

250877196.0392704904

result:

ok found '250877196.0392705', expected '250877196.0392705', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed