QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75476#5461. Paddle Staryuto1115AC ✓191ms4236kbC++1718.8kb2023-02-05 12:18:162023-02-05 12:18:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 12:18:18]
  • 评测
  • 测评结果:AC
  • 用时:191ms
  • 内存:4236kb
  • [2023-02-05 12:18:16]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d)
#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--)
#define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--)
#define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d)
#define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SORT(a) sort(all(a));
#define REV(a) reverse(all(a));
#define SZ(a) int(a.size())
#define popcount(x) __builtin_popcountll(x)
#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define ppf pop_front
#define ppb pop_back
#ifdef __LOCAL
#define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; }
#else
#define debug(...) void(0);
#endif
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
using vlp = vector<LP>;
using vvlp = vector<vlp>;
template<class T>
using PQ = priority_queue<T>;
template<class T>
using PQrev = priority_queue<T, vector<T>, greater<T>>;

template<class S, class T>
istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; }

template<class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; }

template<class S, class T, class U>
istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); }

template<class S, class T, class U>
ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {
    return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';
}

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &t: v) { is >> t; }
    return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '[';
    rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
    return os << ']';
}

template<class T>
ostream &operator<<(ostream &os, const deque<T> &v) {
    os << '[';
    rep(i, v.size()) os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
    return os << ']';
}

template<class T>
ostream &operator<<(ostream &os, const set<T> &st) {
    os << '{';
    auto it = st.begin();
    while (it != st.end()) {
        os << (it == st.begin() ? "" : ", ") << *it;
        it++;
    }
    return os << '}';
}

template<class T>
ostream &operator<<(ostream &os, const multiset<T> &st) {
    os << '{';
    auto it = st.begin();
    while (it != st.end()) {
        os << (it == st.begin() ? "" : ", ") << *it;
        it++;
    }
    return os << '}';
}

template<class T, class U>
ostream &operator<<(ostream &os, const map<T, U> &mp) {
    os << '{';
    auto it = mp.begin();
    while (it != mp.end()) {
        os << (it == mp.begin() ? "" : ", ") << *it;
        it++;
    }
    return os << '}';
}

template<class T>
void vecout(const vector<T> &v, char div = '\n') {
    rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div);
}

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

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

void scan() {}

template<class Head, class... Tail>
void scan(Head &head, Tail &... tail) {
    cin >> head;
    scan(tail...);
}

template<class T>
void print(const T &t) { cout << t << '\n'; }

template<class Head, class... Tail>
void print(const Head &head, const Tail &... tail) {
    cout << head << ' ';
    print(tail...);
}

template<class T>
vector<T> &operator+=(vector<T> &v, T x) {
    for (T &t: v) t += x;
    return v;
}

template<class T>
vector<T> &operator-=(vector<T> &v, T x) {
    for (T &t: v) t -= x;
    return v;
}

template<class T>
vector<T> &operator*=(vector<T> &v, T x) {
    for (T &t: v) t *= x;
    return v;
}

template<class T>
vector<T> &operator/=(vector<T> &v, T x) {
    for (T &t: v) t /= x;
    return v;
}

struct Init_io {
    Init_io() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cout << boolalpha << fixed << setprecision(15);
        cerr << boolalpha << fixed << setprecision(15);
    }
} init_io;

const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int inf = 1001001001;
const ll linf = 1001001001001001001;

void rearrange(const vi &) {}

template<class T, class... Tail>
void rearrange(const vi &ord, vector<T> &head, Tail &...tail) {
    assert(ord.size() == head.size());
    vector<T> ori = head;
    rep(i, ord.size()) head[i] = ori[ord[i]];
    rearrange(ord, tail...);
}

template<class T, class... Tail>
void sort_by(vector<T> &head, Tail &... tail) {
    vi ord(head.size());
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j) { return head[i] < head[j]; });
    rearrange(ord, head, tail...);
}

bool in_rect(int i, int j, int h, int w) {
    return 0 <= i and i < h and 0 <= j and j < w;
}

template<class T>
constexpr vector<T> pow_table(int n, T base) {
    vector<T> res(n, 1);
    rep(i, n - 1) res[i + 1] = res[i] * base;
    return res;
}

template<class T, class S>
vector<T> cumsum(const vector<S> &v, bool shift_one = true) {
    int n = v.size();
    vector<T> res;
    if (shift_one) {
        res.resize(n + 1);
        rep(i, n) res[i + 1] = res[i] + v[i];
    } else {
        res.resize(n);
        if (n) {
            res[0] = v[0];
            rep(i, 1, n) res[i] = res[i - 1] + v[i];
        }
    }
    return res;
}

vvi graph(int n, int m, bool directed = false, int origin = 1) {
    vvi G(n);
    rep(_, m) {
        INT(u, v);
        u -= origin, v -= origin;
        G[u].pb(v);
        if (!directed) G[v].pb(u);
    }
    return G;
}

template<class T>
vector<vector<pair<int, T>>> weighted_graph(int n, int m, bool directed = false, int origin = 1) {
    vector<vector<pair<int, T>>> G(n);
    rep(_, m) {
        int u, v;
        T w;
        scan(u, v, w);
        u -= origin, v -= origin;
        G[u].eb(v, w);
        if (!directed) G[v].eb(u, w);
    }
    return G;
}

const double eps = 1e-9;
const double PI = acos(-1);

int sgn(double a) { return a < -eps ? -1 : (a > eps ? 1 : 0); }

double to_rad(double deg) { return deg * PI / 180; }

double to_deg(double rad) { return rad * 180 / PI; }

struct point {
    double x, y;
    
    point(double x = 0, double y = 0) : x(x), y(y) {}
    
    point operator+(const point &p) const { return {x + p.x, y + p.y}; }
    
    point operator-(const point &p) const { return {x - p.x, y - p.y}; }
    
    point operator*(double a) const { return {x * a, y * a}; }
    
    point operator*(const point &p) const { return point(x * p.x - y * p.y, x * p.y + y * p.x); }
    
    point operator/(double a) const { return {x / a, y / a}; }
    
    point operator-() const { return *this * (-1); }
    
    bool operator==(const point &p) const { return !sgn(x - p.x) && !sgn(y - p.y); }
    
    bool operator!=(const point &p) const { return !(*this == p); }
    
    bool operator<(const point &p) const { return sgn(x - p.x) ? x < p.x : y < p.y; }
    
    bool operator>(const point &p) const { return sgn(x - p.x) ? x > p.x : y > p.y; }
    
    double norm() const { return x * x + y * y; }
    
    double abs() const { return sqrt(norm()); }
    
    point rot(double rad) const { return point(cos(rad) * x - sin(rad) * y, sin(rad) * x + cos(rad) * y); }
    
    point rot90() const { return point(-y, x); }
    
    double arg() const {
        double res = atan2(y, x);
        if (sgn(res) < 0) res += 2 * PI;
        return res;
    }
};

istream &operator>>(istream &is, point &p) { return is >> p.x >> p.y; }

ostream &operator<<(ostream &os, const point &p) { return os << '(' << p.x << "," << p.y << ')'; }

double dist(const point &a, const point &b) { return (a - b).abs(); }

double dot(const point &a, const point &b) { return a.x * b.x + a.y * b.y; }

double cross(const point &a, const point &b) { return a.x * b.y - a.y * b.x; }

point mid(const point &a, const point &b) { return (a + b) / 2; }

int ccw(const point &a, const point &b, const point &c) {
    // 1 -> c is upper than line(a,b)
    // -1 -> c is lower than line(a,b)
    // 2 -> in order [a,b,c]
    // -2 -> in order [c,a,b]
    // 0 -> in order [a,c,b]
    point nb = b - a, nc = c - a;
    if (sgn(cross(nb, nc))) return sgn(cross(nb, nc));
    if (sgn(dot(nb, nc)) < 0) return -2;
    if (sgn(nc.abs() - nb.abs()) > 0) return 2;
    return 0;
}

struct line {
    point a, b;
    
    line(point a = point(), point b = point()) : a(a), b(b) {}
    
    bool online(const point &p) const { return abs(ccw(a, b, p)) != 1; }
};

ostream &operator<<(ostream &os, const line &l) { return os << '{' << l.a << ',' << l.b << '}'; }

struct segment {
    point a, b;
    
    segment(point a = point(), point b = point()) : a(a), b(b) {}
    
    bool online(const point &p) const { return !ccw(a, b, p); }
    
    line vertical_bisector() const { return line(mid(a, b), mid(a, b) + (b - a).rot90()); }
};

ostream &operator<<(ostream &os, const segment &l) { return os << '{' << l.a << ',' << l.b << '}'; }

bool vertical(const line &l, const line &m) { return !sgn(dot(l.a - l.b, m.a - m.b)); }

bool vertical(const segment &l, const segment &m) { return !sgn(dot(l.a - l.b, m.a - m.b)); }

bool parallel(const line &l, const line &m) { return !sgn(cross(l.a - l.b, m.a - m.b)); }

bool parallel(const segment &l, const segment &m) { return !sgn(cross(l.a - l.b, m.a - m.b)); }

bool operator==(const line &l, const line &m) { return parallel(l, m) && l.online(m.a); }

bool operator!=(const line &l, const line &m) { return !(l == m); }

bool operator==(const segment &l, const segment &m) { return l.a == m.a && l.b == m.b || l.a == m.b && l.b == m.a; }

bool operator!=(const segment &l, const segment &m) { return !(l == m); }

// intersect at one point
bool intersect(const line &l, const line &m) { return !parallel(l, m); }

bool intersect(const line &l, const segment &m) {
    return sgn(cross(l.b - l.a, m.a - l.a) * cross(l.b - l.a, m.b - l.a)) <= 0;
}

bool intersect(const segment &l, const segment &m) {
    return ccw(l.a, l.b, m.a) * ccw(l.a, l.b, m.b) <= 0 &&
           ccw(m.a, m.b, l.a) * ccw(m.a, m.b, l.b) <= 0;
}

point intersection(const line &l, const line &m) {
    assert(intersect(l, m));
    return l.a + (l.b - l.a) * cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, l.b - l.a);
}

point intersection(const line &l, const segment &m) {
    assert(intersect(l, m));
    return l.a + (l.b - l.a) * cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, l.b - l.a);
}

point intersection(const segment &l, const segment &m) {
    assert(intersect(l, m));
    return l.a + (l.b - l.a) * cross(m.b - m.a, m.a - l.a) / cross(m.b - m.a, l.b - l.a);
}

double dist(const line &l, const point &p) { return abs(cross(l.b - l.a, p - l.a)) / (l.b - l.a).abs(); }

double dist(const segment &l, const point &p) {
    if (sgn(dot(l.b - l.a, p - l.a)) < 0) return dist(p, l.a);
    if (sgn(dot(l.a - l.b, p - l.b)) < 0) return dist(p, l.b);
    return dist(line(l.a, l.b), p);
}

double dist(const line &l, const line &m) {
    if (parallel(l, m)) return dist(l, m.a);
    return 0;
}

double dist(const line &l, const segment &m) {
    if (intersect(l, m)) return 0;
    return min(dist(l, m.a), dist(l, m.b));
}

double dist(const segment &l, const segment &m) {
    if (intersect(l, m)) return 0;
    return min({dist(l, m.a), dist(l, m.b), dist(m, l.a), dist(m, l.b)});
}

point projection(const line &l, const point &p) {
    double d = dot(p - l.a, l.b - l.a) / (l.b - l.a).norm();
    return l.a + (l.b - l.a) * d;
}

point circumcenter(const point &a, const point &b, const point &c) {
    return intersection(segment(a, b).vertical_bisector(), segment(b, c).vertical_bisector());
}

struct circle {
    point o;
    double r;
    
    circle(point o = point(), double r = 0) : o(o), r(r) {}
    
    bool inside(const point &p) const { return sgn(r - dist(o, p)) >= 0; }
    
    double area() const { return r * r * PI; }
};

ostream &operator<<(ostream &os, const circle &c) { return os << '{' << c.o << ',' << c.r << '}'; }

bool intersect(const circle &c, const line &l) { return sgn(dist(l, c.o) - c.r) <= 0; }

bool intersect(const circle &c, const segment &l) {
    if (sgn(dist(l, c.o) - c.r) > 0) return false;
    return sgn(max((c.o - l.a).abs(), (c.o - l.b).abs()) - c.r) >= 0;
}

vector<point> intersection(const circle &c, const line &l) {
    point p = projection(l, c.o);
    if (!intersect(c, l)) return {};
    if (sgn(dist(l, c.o) - c.r) == 0) return {p};
    point e = (l.b - l.a) / (l.b - l.a).abs();
    double d = sqrt(c.r * c.r - (p - c.o).norm());
    return {p - e * d, p + e * d};
}

vector<point> intersection(const circle &c, const segment &l) {
    auto v = intersection(c, line(l.a, l.b));
    vector<point> ret;
    for (point p: v) if (l.online(p)) ret.pb(p);
    return ret;
}

vector<point> intersection(const circle &a, const circle &b) {
    double d = dist(a.o, b.o);
    if (!sgn(a.r + b.r - d)) return {a.o + (b.o - a.o) * a.r / d};
    if (!sgn(a.r - b.r - d)) return {a.o + (b.o - a.o) * a.r / d};
    if (!sgn(b.r - a.r - d)) return {b.o + (a.o - b.o) * b.r / d};
    if (sgn(abs(a.r - b.r) - d) > 0 || sgn(a.r + b.r - d) < 0) return {};
    double x = (a.r * a.r + d * d - b.r * b.r) / (2 * d);
    double y = sqrt(a.r * a.r - x * x);
    point p = (b.o - a.o).rot90() * y / d;
    point to_mid = a.o + (b.o - a.o) * x / d;
    return {to_mid - p, to_mid + p};
}

vector<circle> circle_with_two_points_and_radius(const point &a, const point &b, const double &r) {
    if (sgn(dist(a, b) - 2 * r) > 0) return {};
    circle A(a, r), B(b, r);
    auto v = intersection(A, B);
    vector<circle> ret;
    for (point p: v) ret.eb(p, r);
    return ret;
};

vector<point> tangent_point(const circle &c, const point &p) {
    int s = sgn(dist(c.o, p) - c.r);
    if (s < 0) return {};
    if (s == 0) return {p};
    double d = (p - c.o).norm() - c.r * c.r;
    return intersection(c, circle(p, sqrt(d)));
}

vector<line> tangent_line(const circle &c, const point &p) {
    vector<point> v = tangent_point(c, p);
    if (v.empty()) return {};
    if (v.size() == 1) return {line(p, p + (c.o - p).rot90())};
    vector<line> res;
    for (auto tp: v) res.eb(p, tp);
    return res;
}

vector<line> tangent_line(const circle &a, const circle &b) {
    if (sgn(a.r - b.r) < 0) return tangent_line(b, a);
    double ar = a.r, br = b.r, d = dist(a.o, b.o);
    if (sgn(d - (ar - br)) < 0) return {};
    else if (sgn(d - (ar - br)) == 0) {
        point p = (a.o * (-br) + b.o * ar) / (ar - br);
        return {line(p, p + (a.o - p).rot90())};
    } else {
        vector<line> res;
        {
            double theta = acos((ar - br) / d);
            {
                point p = a.o + ((b.o - a.o) / d * ar).rot(-theta);
                res.eb(p, p + (a.o - p).rot90());
            }
            {
                point p = a.o + ((b.o - a.o) / d * ar).rot(theta);
                res.eb(p, p + (a.o - p).rot90());
            }
        }
        if (sgn(d - (ar + br)) >= 0) {
            point p = (a.o * br + b.o * ar) / (ar + br);
            vector<line> lines = tangent_line(a, p);
            for (line l: lines) res.pb(l);
        }
        return res;
    }
}

vector<point> convex_hull(vector<point> v) {
    sort(all(v));
    int n = v.size(), k = 0;
    vector<point> res(2 * n);
    for (int i = 0; i < n; res[k++] = v[i++])
        while (k > 1 && ccw(res[k - 2], res[k - 1], v[i]) <= 0) k--;
    for (int i = n - 2, t = k; i >= 0; res[k++] = v[i--])
        while (k > t && ccw(res[k - 2], res[k - 1], v[i]) <= 0) k--;
    res.resize(k - 1);
    return res;
}

double fan_shaped(double r, double theta) {
    return r * r * theta / 2;
}

void solve() {
    DBL(l1, l2, a, b);
    a = a / 180 * PI;
    b = b / 180 * PI;
    double ans = 0;
    if (b <= PI / 2 + 1e-7) {
        ans += fan_shaped(l1 + l2, 2 * a);
        ans += fan_shaped(l2, 2 * b);
    } else {
        ans += fan_shaped(l1 + l2, 2 * a);
        ans += fan_shaped(l2, 2 * b);
        ans += l1 * l2 * sin(PI - b);
        double r = sqrt(l1 * l1 + l2 * l2 - 2. * l1 * l2 * cos(PI - b));
        double c = asin(sin(b) * l2 / r);
        if (c <= b - PI / 2 + 1e-7) {
            if (2 * a >= c - 1e-7) {
                ans -= fan_shaped(r, 2 * c);
            } else {
                segment X(point(l1, 0), point(0, 0));
                point p(l1 * cos(-2 * a), l1 * sin(-2 * a));
                point q(l2 * cos(-2 * a + b), l2 * sin(-2 * a + b));
                segment Y(p, p + q);
                double d = intersection(X, Y).x;
                ans -= r * d * sin(c - 2 * a);
                ans -= fan_shaped(r, 4 * a);
            }
        } else if (2 * a >= b - PI / 2 - 1e-7) {
            ans -= r * r * sin(c - (b - PI / 2)) * cos(c - (b - PI / 2));
            ans -= fan_shaped(r * cos(c - (b - PI / 2)), 2 * b - PI);
        } else {
            ans -= r * r * sin(c - (b - PI / 2)) * cos(c - (b - PI / 2));
            ans -= fan_shaped(r * cos(c - (b - PI / 2)), 4 * a);
            ans -= r * r * cos(c - (b - PI / 2)) * cos(c - (b - PI / 2)) * tan(b - PI / 2 - 2 * a);
        }
    }
    print(ans);
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}

詳細信息

Test #1:

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

input:

5
2 1 20 20
3 3 0 0
20 20 90 120
20 10 50 170
100 10 1 93

output:

3.490658503988659
0.000000000000000
3367.157611906510738
1098.863278984081944
373.960489570088157

result:

ok 5 numbers

Test #2:

score: 0
Accepted
time: 176ms
memory: 4076kb

input:

100000
88 12 24 116
79 15 84 150
96 52 31 141
100 100 81 29
83 29 71 99
95 92 5 87
99 97 39 72
79 72 20 65
67 39 60 116
100 89 1 62
78 77 63 45
62 34 83 178
92 49 24 103
94 73 66 49
20 14 24 51
100 97 66 109
94 94 86 82
82 79 49 67
76 38 88 118
92 79 58 112
93 23 40 167
87 34 13 25
96 18 73 15
94 38...

output:

4526.991613202875669
13636.479265474325075
19433.170502612672863
61610.122595399836428
17006.233726987324189
15903.667036975090014
37972.639843450066110
13840.111902464634113
14968.804520318268260
9194.795925234087917
31073.492936656642996
16982.120743226401828
12675.930420194696126
36683.2429519542...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 140ms
memory: 4044kb

input:

100000
1 1 0 0
1 1 0 1
1 1 0 2
1 1 0 3
1 1 0 4
1 1 0 5
1 1 0 6
1 1 0 7
1 1 0 8
1 1 0 9
1 1 0 10
1 1 0 11
1 1 0 12
1 1 0 13
1 1 0 14
1 1 0 15
1 1 0 16
1 1 0 17
1 1 0 18
1 1 0 19
1 1 0 20
1 1 0 21
1 1 0 22
1 1 0 23
1 1 0 24
1 1 0 25
1 1 0 26
1 1 0 27
1 1 0 28
1 1 0 29
1 1 0 30
1 1 0 31
1 1 0 32
1 1 0 ...

output:

0.000000000000000
0.017453292519943
0.034906585039887
0.052359877559830
0.069813170079773
0.087266462599716
0.104719755119660
0.122173047639603
0.139626340159546
0.157079632679490
0.174532925199433
0.191986217719376
0.209439510239320
0.226892802759263
0.244346095279206
0.261799387799149
0.2792526803...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 134ms
memory: 4116kb

input:

100000
1 1 0 0
1 1 0 1
1 1 0 2
1 1 0 3
1 1 0 4
1 1 0 5
1 1 0 6
1 1 0 7
1 1 0 8
1 1 0 9
1 1 0 10
1 1 0 11
1 1 0 12
1 1 0 13
1 1 0 14
1 1 0 15
1 1 0 16
1 1 0 17
1 1 0 18
1 1 0 19
1 1 0 20
1 1 0 21
1 1 0 22
1 1 0 23
1 1 0 24
1 1 0 25
1 1 0 26
1 1 0 27
1 1 0 28
1 1 0 29
1 1 0 30
1 1 0 31
1 1 0 32
1 1 0 ...

output:

0.000000000000000
0.017453292519943
0.034906585039887
0.052359877559830
0.069813170079773
0.087266462599716
0.104719755119660
0.122173047639603
0.139626340159546
0.157079632679490
0.174532925199433
0.191986217719376
0.209439510239320
0.226892802759263
0.244346095279206
0.261799387799149
0.2792526803...

result:

ok 100000 numbers

Test #5:

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

input:

1
1 1 0 0

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

score: 0
Accepted
time: 152ms
memory: 4076kb

input:

100000
2 1 24 89
3 1 76 68
2 2 52 144
3 3 4 2
2 2 86 44
3 2 87 123
3 2 2 53
3 1 50 172
3 3 86 156
2 2 46 1
3 3 74 71
2 2 20 104
2 2 29 86
3 3 2 30
2 2 26 178
3 2 14 108
3 3 90 69
3 2 13 175
3 3 52 35
2 2 73 31
3 3 77 105
3 1 86 143
3 3 50 109
3 1 13 94
3 2 41 139
2 2 51 154
2 1 57 40
3 3 27 112
2 2 ...

output:

5.323254218582705
22.410027595607193
25.173876620134230
2.827433388230814
27.087509990951997
47.012886069756902
4.572762640225143
17.101525659348557
80.168864241397912
12.915436464758038
57.648225193372703
12.864384636389129
14.102260356114183
5.969026041820607
19.818865672108203
13.736070861025445
...

result:

ok 100000 numbers

Test #7:

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

input:

1
1 1 1 1

output:

0.087266462599716

result:

ok found '0.0872665', expected '0.0872665', error '0.0000000'

Test #8:

score: 0
Accepted
time: 185ms
memory: 4232kb

input:

100000
71 6 33 34
98 20 79 171
88 16 59 8
45 21 36 79
88 61 44 149
55 47 72 86
81 8 85 122
68 2 35 71
98 91 79 49
73 19 68 148
69 66 81 22
99 94 87 130
65 53 43 53
97 89 84 1
93 88 77 6
83 46 2 51
83 69 46 95
91 55 17 137
93 84 1 54
61 45 74 15
77 65 0 21
84 71 6 32
87 81 37 76
91 55 32 154
73 34 76...

output:

3436.221684618956260
20453.899714220959140
11173.458244927538544
3345.010777909732042
27858.125443027409347
16389.723780362990510
11913.368920826427711
2998.196402245938771
56334.480958811531309
11128.116724082297878
27437.570679024494893
77419.259170279998216
13048.238567542288365
50858.63260372696...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 164ms
memory: 4208kb

input:

100000
10 1 40 160
6 6 27 16
10 10 7 41
4 1 38 161
7 6 66 143
6 4 26 127
8 4 47 99
4 4 49 121
5 2 68 122
8 8 27 178
10 8 73 125
6 2 20 175
10 1 34 13
7 4 66 102
10 10 14 179
9 7 64 120
7 5 47 169
10 8 68 90
8 2 37 3
5 5 10 164
4 2 26 62
7 5 43 40
1 1 35 103
10 7 71 102
6 1 90 63
6 4 49 44
6 3 84 123...

output:

87.584913357908221
77.911497809026869
120.427718387608735
19.690923988660575
291.658182925004439
83.318489580253342
145.851363237234608
89.226195379333817
67.671999442581239
321.571228728411654
558.426573154582115
34.903934826530360
72.029738229805986
168.011900637172886
411.827515292429894
391.8455...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 181ms
memory: 3988kb

input:

100000
8 8 89 18
10 1 17 44
6 1 43 5
11 10 84 74
11 11 64 172
10 7 85 51
7 6 71 176
9 7 51 99
5 3 12 54
6 5 26 32
3 2 21 23
10 10 59 151
9 9 81 45
7 4 2 37
11 6 3 172
11 10 65 98
11 10 78 173
7 2 9 104
10 9 46 77
8 3 24 100
11 9 77 41
10 10 55 30
11 6 37 75
9 7 25 56
10 9 14 7
9 9 12 179
11 9 6 130
...

output:

417.762009757362705
36.669367584400867
36.861353802120234
775.694132756359750
917.192986614324809
472.355908759745375
322.464590122768186
312.639212169688960
21.886428820008895
68.870692283696243
10.768681484805013
692.821232732176441
521.661460128585190
14.556045961632709
127.726396981380759
671.44...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 179ms
memory: 4220kb

input:

100000
7 3 55 160
4 3 14 72
9 7 4 52
9 9 31 71
12 1 87 116
9 7 10 154
12 10 20 100
6 5 61 69
12 12 55 130
12 11 7 163
4 3 43 178
11 11 42 155
12 1 20 1
5 3 72 151
7 2 74 136
10 10 66 76
11 11 84 176
8 6 59 110
12 2 54 47
12 12 38 28
12 12 38 105
12 12 60 173
12 4 48 76
2 1 71 31
3 1 21 123
12 7 83 2...

output:

123.848168841706794
23.282692221604357
62.343160881237452
275.674755352504349
258.992530853761480
187.418244337319635
343.731350761198883
158.929681686603629
891.558109336301413
425.573601551489446
65.047404023752421
703.955421939028611
59.009582009928288
107.152855427087019
115.790851181557642
593....

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 160ms
memory: 4064kb

input:

100000
12 8 12 17
7 1 3 24
13 13 40 16
9 9 77 68
11 1 2 137
8 5 43 153
11 10 60 93
9 4 54 124
13 11 90 62
13 11 23 10
9 5 65 152
13 10 81 159
9 5 0 100
2 1 8 10
13 4 29 108
11 9 33 62
1 1 7 0
7 6 9 117
10 7 79 17
6 3 44 136
9 1 89 169
12 12 90 59
11 11 67 48
8 2 50 165
12 3 36 39
11 2 46 157
12 7 57...

output:

102.764986357426139
3.769911184307752
519.130732713193424
531.557476987393102
7.895855251232727
201.659447813743526
624.135520745836288
197.885993911459337
1035.713284718475052
252.339703253340190
297.248770789876176
1051.611431187916423
43.633231299858238
1.431169986635350
178.080101488159528
318.0...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 180ms
memory: 4176kb

input:

100000
16 6 41 45
19 4 51 119
1 1 20 49
20 20 68 30
20 20 56 133
16 6 69 27
13 12 17 12
11 6 33 146
12 9 51 156
7 7 6 125
20 17 76 123
20 13 14 80
20 20 50 160
10 9 89 177
13 4 0 61
18 4 65 36
10 5 34 167
17 15 73 74
18 1 26 107
17 8 6 65
10 5 14 130
19 6 51 73
11 1 75 177
14 3 76 96
8 3 31 9
7 5 13...

output:

374.617470648062920
509.228455427212339
2.251474735072685
2108.357736409150220
2531.274337012177966
599.834757325411147
215.600522498859533
270.926866137202694
635.711065501702819
129.606175914049857
2456.987219221100077
502.061412628688856
2584.665518016392070
815.152005832541136
17.034413499464655...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 177ms
memory: 4176kb

input:

100000
21 19 6 6
17 6 48 147
16 10 56 89
18 18 89 19
19 18 79 85
15 7 12 18
20 18 57 117
17 16 36 117
9 6 12 81
20 19 4 76
19 18 7 97
21 2 79 160
21 19 5 4
21 19 25 119
14 10 54 129
21 17 49 21
21 13 48 179
14 14 31 80
18 17 51 1
8 4 37 1
13 9 90 118
14 14 47 64
16 11 3 74
20 15 30 42
19 19 38 133
1...

output:

205.355439789652849
550.064867878033851
816.046145062468781
2120.575041173110094
2368.254715323625533
116.762526958420651
2110.323177930085876
1215.784171253938894
98.017690792001559
585.034365268499300
715.994457120842981
741.835073303215495
164.828894558344501
1464.155538987371301
783.297607028993...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 161ms
memory: 4120kb

input:

100000
14 12 55 44
19 19 55 175
18 18 25 53
18 12 61 16
22 19 85 30
21 17 53 122
22 22 80 110
20 17 46 87
19 11 64 165
5 1 20 110
19 6 46 176
22 22 45 164
22 18 77 35
22 4 69 53
17 2 34 93
22 17 33 179
16 12 79 106
17 17 64 87
22 16 60 76
12 4 43 109
18 10 51 174
11 8 60 26
19 17 5 46
14 12 75 101
2...

output:

759.497477297852356
2516.027606494228166
865.194616798629113
998.398145310836185
2682.832859703083614
1972.151629880214387
3638.749115892898317
1537.931776979843107
1382.218152879955142
14.689817208968933
614.867582302067603
2986.650744477979515
2348.165975633171001
828.891768357147043
220.728142886...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 176ms
memory: 4044kb

input:

100000
22 20 49 129
22 1 9 42
29 27 41 134
29 29 72 80
27 16 71 123
28 7 21 71
25 13 70 133
28 11 27 60
29 28 68 3
23 5 1 168
27 22 79 16
29 10 17 81
27 15 90 119
29 28 86 79
22 21 69 122
27 27 49 139
16 8 11 97
16 11 4 58
12 11 32 128
18 8 35 146
29 22 27 19
30 15 50 115
15 2 24 72
18 6 80 158
13 6...

output:

2446.922149155350326
83.828163973287644
4035.070122674870163
5401.584595412210547
2878.481412038129292
509.705954752424077
2207.415857830733785
843.465267611299623
3897.040967023019221
91.368440291688856
3445.681369164765329
592.661454099714547
3265.055309950067112
5957.681401682644719
3188.83092130...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 169ms
memory: 4012kb

input:

100000
39 35 57 118
18 2 33 138
37 28 62 114
40 2 11 130
11 9 78 113
23 17 47 122
29 7 65 143
36 27 11 77
24 19 77 38
34 30 5 12
12 2 74 14
38 31 37 82
36 34 15 85
39 27 17 161
37 15 46 80
40 14 33 54
37 30 88 95
40 22 9 111
36 36 12 52
40 40 48 151
40 39 41 163
21 16 42 73
18 2 64 146
40 37 84 152
...

output:

8021.612925242914571
241.910091287405749
6161.900464289473348
349.647106948921362
706.655863042590795
1953.103910453777416
1613.995982469010642
1741.698967150181488
2724.301882730469515
545.938990023826250
254.119939090374402
4449.874007592223279
2997.777523225460300
3534.158747180425507
2485.069602...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 171ms
memory: 4236kb

input:

100000
9 8 74 2
47 41 64 61
42 1 75 10
33 29 33 75
43 1 76 103
48 12 73 90
50 50 35 160
50 48 13 179
49 46 77 169
30 18 74 55
44 43 77 164
15 2 31 91
49 43 31 120
49 36 39 131
43 8 23 142
33 31 25 74
25 6 58 129
28 20 31 95
8 7 1 148
37 10 52 156
11 5 54 52
49 26 33 2
20 17 13 33
38 23 89 34
50 7 60...

output:

375.490135274060037
10439.809093851721627
2420.509873128336039
3314.851488435270312
2570.010106911052844
4812.919945299563551
13536.165609610958199
9417.110876737315266
18693.856547754672647
3286.734234185641526
15787.461796313238665
162.717444833826420
8548.794250962400838
8091.250708603429302
1231...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 189ms
memory: 4236kb

input:

100000
985040437 963837006 74 178
562320397 456498961 21 57
616458849 43215539 12 112
967049313 962181597 55 20
404875500 323494205 16 148
822013814 350801410 65 117
493753261 325808227 72 151
883524417 55981080 1 165
756475575 306464991 75 65
982861539 971158777 53 2
977914232 494619050 34 80
92912...

output:

7823031139236862976.000000000000000
587759779770854528.000000000000000
95369829970997616.000000000000000
3895961013788279808.000000000000000
443752067877684928.000000000000000
1832058841745101568.000000000000000
1157411971581695232.000000000000000
25211463877824912.000000000000000
158551032347764505...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 191ms
memory: 4220kb

input:

100000
915624482 436335283 31 93
966989692 899762255 14 172
971565321 859650888 86 78
840892426 595383046 16 116
992919354 525701445 9 98
924698821 417910701 18 49
923077550 641792877 68 62
918753914 850646822 29 137
935549247 897719522 87 46
937380829 805246200 55 11
434960395 174040501 0 56
902102...

output:

1298002666918419968.000000000000000
3375253522633562624.000000000000000
6039368287407980544.000000000000000
1313133658442171904.000000000000000
835838455087290240.000000000000000
715665701891950464.000000000000000
3352034067230078976.000000000000000
3413794084111542272.000000000000000
57502924204049...

result:

ok 100000 numbers