QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73941#5443. Security at Museumsyuto1115AC ✓657ms5056kbC++1717.5kb2023-01-29 17:30:512023-01-29 17:30:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-29 17:30:52]
  • 评测
  • 测评结果:AC
  • 用时:657ms
  • 内存:5056kb
  • [2023-01-29 17:30:51]
  • 提交

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>
void fin(const T &... a) {
    print(a...);
    exit(0);
}

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, 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;
}

template<int mod>
class modint {
    ll x;
public:
    constexpr modint(ll x = 0) : x((x % mod + mod) % mod) {}
    
    static constexpr int get_mod() { return mod; }
    
    constexpr int val() const { return x; }
    
    constexpr modint operator-() const { return modint(-x); }
    
    constexpr modint &operator+=(const modint &a) {
        if ((x += a.val()) >= mod) x -= mod;
        return *this;
    }
    
    constexpr modint &operator++() { return *this += 1; }
    
    constexpr modint &operator-=(const modint &a) {
        if ((x += mod - a.val()) >= mod) x -= mod;
        return *this;
    }
    
    constexpr modint &operator--() { return *this -= 1; }
    
    constexpr modint &operator*=(const modint &a) {
        (x *= a.val()) %= mod;
        return *this;
    }
    
    constexpr modint operator+(const modint &a) const {
        modint res(*this);
        return res += a;
    }
    
    constexpr modint operator-(const modint &a) const {
        modint res(*this);
        return res -= a;
    }
    
    constexpr modint operator*(const modint &a) const {
        modint res(*this);
        return res *= a;
    }
    
    constexpr modint pow(ll t) const {
        modint res = 1, a(*this);
        while (t > 0) {
            if (t & 1) res *= a;
            t >>= 1;
            a *= a;
        }
        return res;
    }
    
    template<int m>
    friend istream &operator>>(istream &, modint<m> &);
    
    // for prime mod
    constexpr modint inv() const { return pow(mod - 2); }
    
    constexpr modint &operator/=(const modint &a) { return *this *= a.inv(); }
    
    constexpr modint operator/(const modint &a) const {
        modint res(*this);
        return res /= a;
    }
    
    // constraints : mod = 2 or val = 0 or val^((mod-1)/2) ≡ 1
    //               mod is prime
    // time complexity : O(log^2 p)
    // reference : https://nyaannyaan.github.io/library/modulo/mod-sqrt.hpp
    modint sqrt() const {
        if (x < 2) return x;
        assert(this->pow((mod - 1) >> 1).val() == 1);
        modint b = 1;
        while (b.pow((mod - 1) >> 1).val() == 1) b += 1;
        ll m = mod - 1, e = 0;
        while (~m & 1) m >>= 1, e += 1;
        modint X = this->pow((m - 1) >> 1);
        modint Y = (*this) * X * X;
        X *= *this;
        modint Z = b.pow(m);
        while (Y.val() != 1) {
            ll j = 0;
            modint t = Y;
            while (t.val() != 1) {
                j += 1;
                t *= t;
            }
            Z = Z.pow(1LL << (e - j - 1));
            X *= Z;
            Z *= Z;
            Y *= Z;
            e = j;
        }
        return X;
    }
};

using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;

template<int mod>
istream &operator>>(istream &is, modint<mod> &a) {
    ll x;
    is >> x;
    a = modint<mod>(x);
    return is;
}

template<int mod>
constexpr ostream &operator<<(ostream &os, const modint<mod> &a) { return os << a.val(); }

template<int mod>
constexpr bool operator==(const modint<mod> &a, const modint<mod> &b) { return a.val() == b.val(); }

template<int mod>
constexpr bool operator!=(const modint<mod> &a, const modint<mod> &b) { return a.val() != b.val(); }

template<int mod>
constexpr modint<mod> &operator++(modint<mod> &a) { return a += 1; }

template<int mod>
constexpr modint<mod> &operator--(modint<mod> &a) { return a -= 1; }

using mint = modint998244353;

using vm = vector<mint>;
using vvm = vector<vm>;

using point = LP;

ll cross(const point &a, const point &b) {
    return a.first * b.second - a.second * b.first;
}

ll dot(const point &a, const point &b) {
    return a.first * b.first + a.second * b.second;
}

ll norm(const point &p) {
    return p.first * p.first + p.second * p.second;
}

int sgn(ll l) {
    if (l < 0) return -1;
    if (l == 0) return 0;
    return 1;
}

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.first - a.first, b.second - a.second};
    point nc = {c.first - a.first, c.second - a.second};
    if (sgn(cross(nb, nc))) return sgn(cross(nb, nc));
    if (sgn(dot(nb, nc)) < 0) return -2;
    if (sgn(norm(nc) - norm(nb)) > 0) return 2;
    return 0;
}

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); }
};

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

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;
}

// [-pi, pi)
// no (0, 0)
bool arg_cmp(const LP &a, const LP &b) {
    int ua = a.second > 0 or (a.second == 0 and a.first > 0);
    int ub = b.second > 0 or (b.second == 0 and b.first > 0);
    if (ua == ub) {
        ll cross = a.first * b.second - a.second * b.first;
        return cross > 0;
    } else {
        return ua < ub;
    }
}

class binomial_coefficient {
public:
    vector<mint> fact, ifact;
    
    binomial_coefficient(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
    
    mint P(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[n - k];
    }
    
    mint naive(mint n, int k) {
        mint res = 1;
        rep(i, k) {
            res *= n - i;
            res /= i + 1;
        }
        return res;
    }
    
    mint naive_P(mint n, int k) {
        mint res = 1;
        rep(i, k) {
            res *= n - i;
        }
        return res;
    }
} binom(1000);

int main() {
    INT(n);
    vl x(n), y(n);
    rep(i, n) scan(x[i], y[i]);
    vector<point> pt(n);
    rep(i, n) pt[i] = {x[i], y[i]};
    vvi dir(n, vi(n, -1));
    {
        vector<tuple<int, int, LP>> tmp;
        rep(i, n) rep(j, n) {
                if (i == j) continue;
                tmp.eb(i, j, LP{x[j] - x[i], y[j] - y[i]});
            }
        sort(all(tmp), [](auto a, auto b) { return arg_cmp(get<2>(a), get<2>(b)); });
        int now = -1;
        rep(i, SZ(tmp)) {
            if (i == 0 or arg_cmp(get<2>(tmp[i - 1]), get<2>(tmp[i]))) ++now;
            dir[get<0>(tmp[i])][get<1>(tmp[i])] = now;
        }
    }
    debug(dir);
    // is k in [i,j](ccw)?
    auto in_int = [](int i, int j, int k) {
        if (i <= j) return i <= k and k <= j;
        else return i <= k or k <= j;
    };
    vvi ok(n, vi(n, true));
    rep(i, n) rep(j, i + 1, n) {
            rep(_, 2) {
                int a = (i + n - 1) % n;
                int b = (i + 1) % n;
                ok[i][j] &= in_int(dir[i][b], dir[i][a], dir[i][j]);
                swap(i, j);
            }
            segment s(pt[i], pt[j]);
            rep(k, n) {
                int a = k;
                int b = (k + 1) % n;
                if (s.online(pt[a])) continue;
                if (s.online(pt[b])) continue;
                segment t(pt[a], pt[b]);
                ok[i][j] &= !intersect(s, t);
            }
            rep(k, n) {
                if (i == k or j == k) continue;
                if (!s.online(pt[k])) continue;
                int a = (k + n - 1) % n;
                int b = (k + 1) % n;
                ok[i][j] &= in_int(dir[k][b], dir[k][a], dir[k][i]);
                ok[i][j] &= in_int(dir[k][b], dir[k][a], dir[k][j]);
            }
            ok[i][j] = ok[j][i] = (ok[i][j] & ok[j][i]);
        }
    mint ans;
    auto convex_low = [&](int s) -> vm {
        vp eg;
        rep(i, n) rep(j, n) if (i != j) {
                    if (!ok[i][j]) continue;
                    if (!arg_cmp({0, -1}, {x[j] - x[i], y[j] - y[i]})) continue;
                    if (arg_cmp({0, 1}, {x[j] - x[i], y[j] - y[i]})) continue;
                    eg.eb(i, j);
                }
        sort(all(eg),
             [&](P a, P b) {
                 auto [ai, aj] = a;
                 auto [bi, bj] = b;
                 if (dir[ai][aj] != dir[bi][bj]) return dir[ai][aj] < dir[bi][bj];
                 return pt[ai] < pt[bi];
             });
        vm dp(n);
        dp[s] = 1;
        for (auto [i, j]: eg) {
            dp[j] += dp[i];
        }
        return dp;
    };
    auto convex_up = [&](int s) -> vm {
        vp eg;
        rep(i, n) rep(j, n) if (i != j) {
                    if (!ok[i][j]) continue;
                    if (!arg_cmp({0, -1}, {x[j] - x[i], y[j] - y[i]})) continue;
                    if (arg_cmp({0, 1}, {x[j] - x[i], y[j] - y[i]})) continue;
                    eg.eb(i, j);
                }
        sort(all(eg),
             [&](P a, P b) {
                 auto [ai, aj] = a;
                 auto [bi, bj] = b;
                 if (dir[ai][aj] != dir[bi][bj]) return dir[ai][aj] > dir[bi][bj];
                 return pt[ai] < pt[bi];
             });
        vm dp(n);
        dp[s] = 1;
        for (auto [i, j]: eg) {
            dp[j] += dp[i];
        }
        return dp;
    };
    rep(s, n) {
        vm dpl = convex_low(s);
        vm dpu = convex_up(s);
        debug(s);
        debug(dpl);
        debug(dpu);
        rep(t, n) {
            if (s == t) continue;
            ans += dpl[t] * dpu[t];
        }
    }
    rep(s, n) rep(t, s + 1, n) {
            if (!ok[s][t]) continue;
            int cnt = 0;
            rep(i, n) {
                if (i == s or i == t) continue;
                if (segment(pt[s], pt[t]).online(pt[i])) ++cnt;
            }
            ans -= mint(4).pow(cnt);
            ans += mint(2).pow(cnt);
        }
    fin(ans);
}

詳細信息

Test #1:

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

input:

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

output:

56

result:

ok 1 number(s): "56"

Test #2:

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

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3336kb

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3360kb

input:

4
0 0
-10 0
-10 -10
0 -10

output:

11

result:

ok 1 number(s): "11"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3388kb

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

4
0 0
10 5
20 0
10 10

output:

7

result:

ok 1 number(s): "7"

Test #8:

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

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3280kb

input:

4
-100 -10
100 -10
100 10
-100 10

output:

11

result:

ok 1 number(s): "11"

Test #10:

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

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

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

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

7
0 0
10 10
20 0
30 11
20 22
10 11
0 22

output:

44

result:

ok 1 number(s): "44"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

10
0 0
10 10
20 0
30 10
40 0
40 21
30 11
20 21
10 11
0 21

output:

93

result:

ok 1 number(s): "93"

Test #14:

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

input:

7
0 0
50 50
80 20
110 50
70 90
40 60
0 100

output:

44

result:

ok 1 number(s): "44"

Test #15:

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

input:

16
0 0
20 0
20 10
40 10
40 20
60 20
60 30
70 30
70 40
50 40
50 30
30 30
30 20
10 20
10 10
0 10

output:

407

result:

ok 1 number(s): "407"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

12
0 0
400 0
400 500
0 500
0 200
200 200
200 300
100 300
100 400
300 400
300 100
0 100

output:

51

result:

ok 1 number(s): "51"

Test #17:

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

input:

10
0 500
-10 20
-350 350
-20 0
-350 -350
0 -20
350 -350
20 0
350 350
10 20

output:

93

result:

ok 1 number(s): "93"

Test #18:

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

input:

16
0 0
10 -5
20 0
30 15
40 0
45 10
40 20
25 30
40 40
30 45
20 40
10 25
0 40
-5 30
0 20
15 10

output:

247

result:

ok 1 number(s): "247"

Test #19:

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

input:

8
100 90
90 100
-90 100
-100 90
-100 -90
-90 -100
90 -100
100 -90

output:

247

result:

ok 1 number(s): "247"

Test #20:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

8
0 0
10 100
90 100
100 0
100 201
90 101
10 101
0 201

output:

31

result:

ok 1 number(s): "31"

Test #21:

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

input:

8
0 0
100 100
900 100
1000 0
1000 210
900 110
100 110
0 210

output:

31

result:

ok 1 number(s): "31"

Test #22:

score: 0
Accepted
time: 1ms
memory: 3352kb

input:

3
1000000 -1000000
1000000 1000000
-1000000 -1000000

output:

4

result:

ok 1 number(s): "4"

Test #23:

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

input:

4
1000000 -1000000
1000000 1000000
1 0
-1000000 -1000000

output:

7

result:

ok 1 number(s): "7"

Test #24:

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

input:

4
1000000 -1000000
1000000 1000000
0 1
-1000000 -1000000

output:

11

result:

ok 1 number(s): "11"

Test #25:

score: 0
Accepted
time: 657ms
memory: 5000kb

input:

200
-28269 899556
-52917 898443
-82904 896173
-112799 892903
-139901 889060
-167758 884227
-196328 878325
-220331 872613
-248497 865014
-277258 856229
-302321 847703
-331311 836799
-354953 827048
-381571 815109
-407788 802314
-431209 789973
-455810 776039
-479961 761338
-503639 745887
-529006 728115...

output:

982924531

result:

ok 1 number(s): "982924531"

Test #26:

score: 0
Accepted
time: 654ms
memory: 4968kb

input:

200
-28269 899556
-52917 898443
-82904 896173
-112799 892903
-139901 889060
-167758 884227
-196328 878325
-220331 872613
-248497 865014
-277258 856229
-302321 847703
-331311 836799
-354953 827048
-381571 815109
-407788 802314
-431209 789973
-455810 776039
-479961 761338
-503639 745887
-529006 728115...

output:

491462169

result:

ok 1 number(s): "491462169"

Test #27:

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

input:

200
-1000000 0
-984589 0
-959090 -1000000
-939997 0
-920698 -1000000
-903689 0
-878269 -1000000
-856526 0
-835872 -1000000
-824921 0
-802874 -1000000
-775273 0
-762503 -1000000
-736648 0
-723628 -1000000
-700062 0
-677324 -1000000
-655520 0
-638093 -1000000
-616069 0
-596730 -1000000
-578522 0
-5610...

output:

766756066

result:

ok 1 number(s): "766756066"

Test #28:

score: 0
Accepted
time: 237ms
memory: 4820kb

input:

200
-982632 0
-969103 -1000000
-940842 0
-921682 0
-906001 -1000000
-879789 0
-865042 0
-845192 -1000000
-816404 0
-802606 0
-787373 -1000000
-753645 0
-737956 0
-725228 -1000000
-692298 0
-681026 0
-651636 -1000000
-636348 0
-619790 0
-587407 -1000000
-573321 0
-558772 0
-527808 -1000000
-513494 0
...

output:

399992829

result:

ok 1 number(s): "399992829"

Test #29:

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

input:

7
30 0
30 20
60 40
90 40
90 60
20 50
0 0

output:

40

result:

ok 1 number(s): "40"

Test #30:

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

input:

9
30 0
30 20
20 30
50 50
60 40
90 40
90 60
20 50
0 0

output:

30

result:

ok 1 number(s): "30"

Test #31:

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

input:

10
0 0
400 0
400 200
300 200
300 100
100 100
100 300
400 300
400 400
0 400

output:

41

result:

ok 1 number(s): "41"

Test #32:

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

input:

10
0 -400
400 -400
400 -300
100 -300
100 -100
300 -100
300 -200
400 -200
400 0
0 0

output:

41

result:

ok 1 number(s): "41"

Test #33:

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

input:

20
-2 11
-6 3
-4 2
-1 8
9 3
3 -9
-5 -5
-4 -3
2 -6
6 2
0 5
-2 1
0 0
1 2
3 1
1 -3
-5 0
-8 -6
4 -12
12 4

output:

91

result:

ok 1 number(s): "91"

Test #34:

score: 0
Accepted
time: 111ms
memory: 5020kb

input:

200
-153811 101954
-110538 -13951
-21156 16822
20793 -224637
-105318 -28386
-184845 -25122
-55966 -252174
-65073 -240349
-402588 -55614
-319429 351875
-479382 92012
-213699 555429
112299 348899
687998 510477
379335 468944
157461 420548
102219 458523
148907 488400
610913 530181
430304 566961
821268 5...

output:

1687

result:

ok 1 number(s): "1687"

Test #35:

score: 0
Accepted
time: 110ms
memory: 4896kb

input:

200
122301 113556
338694 233402
368238 131577
446030 331311
535103 535679
781548 843294
666909 875595
442356 427784
374568 306449
-26086 6336
356963 370926
75420 132096
109676 185484
392958 553349
511233 697425
-105084 -25122
16287 361251
338613 501111
251648 493356
589628 908975
16500 972309
535022...

output:

1663

result:

ok 1 number(s): "1663"

Test #36:

score: 0
Accepted
time: 106ms
memory: 5052kb

input:

200
421640 547713
650121 928769
547442 928833
346206 886544
-452730 992357
102138 855965
111368 905793
366936 808814
97664 687998
306486 711903
22692 663762
-57963 885504
-55792 734234
-463485 989088
-157192 737144
-241500 603149
-444462 699033
-203932 580725
37067 568415
339672 708146
497484 744522...

output:

1599

result:

ok 1 number(s): "1599"

Test #37:

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

input:

200
207543 18138
233654 136908
700845 -843115
765038 -961705
480771 -367522
784833 -913671
931941 -853932
718884 -558630
197457 373259
426012 6606
359594 164931
795933 -587514
362999 173610
635496 -231358
517028 -17575
653370 -224637
779784 -468309
814878 -651810
970226 -830284
897312 -690219
653588...

output:

1403

result:

ok 1 number(s): "1403"

Test #38:

score: 0
Accepted
time: 104ms
memory: 4880kb

input:

200
384246 119904
515880 90069
537210 144074
706626 62156
434349 603996
378143 465476
443127 317247
164931 198306
533444 341568
239054 104826
37271 27579
161283 99692
-13462 22109
497481 748134
753303 786567
441458 667358
736625 725172
466416 609863
638721 590361
679778 436017
624801 526664
704712 1...

output:

1703

result:

ok 1 number(s): "1703"

Test #39:

score: 0
Accepted
time: 98ms
memory: 4888kb

input:

200
290300 170277
240567 128495
339132 87891
177572 360968
480771 164259
512115 17961
405629 5648
333267 87849
346164 -61209
737469 -277905
699884 -331989
552159 -233661
67764 13977
51210 -31561
624573 -303696
365547 -415143
596037 -320155
382416 -471408
455414 -430867
473946 -409309
653883 -416259
...

output:

1723

result:

ok 1 number(s): "1723"

Test #40:

score: 0
Accepted
time: 112ms
memory: 4824kb

input:

200
-55665 353610
-95883 490124
132390 -66873
58841 248211
516981 -547989
507597 -169864
509958 -216196
522693 -268425
681047 -280795
494694 -143556
266337 -45390
313914 -52921
223239 1950
194649 346206
384276 367670
369288 321381
762722 -204108
497747 152082
716706 205593
526883 280884
795998 34640...

output:

1959

result:

ok 1 number(s): "1959"

Test #41:

score: 0
Accepted
time: 108ms
memory: 4876kb

input:

200
283343 271859
383730 322703
365793 322247
450695 405629
434937 311613
486618 479943
358449 -12483
67130 -122775
416790 227442
-16551 -180451
295266 -315165
383364 28503
502124 440735
527090 528342
456162 243552
444408 -165328
648036 -459271
561377 -12972
539900 87975
597287 63161
566952 304059
7...

output:

1703

result:

ok 1 number(s): "1703"

Test #42:

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

input:

200
5009 71481
-20981 20885
-12 -30222
-99838 189696
103887 126708
351540 380079
242496 299244
527678 785484
336098 539408
101865 137745
64338 267396
147075 359897
524 197672
520671 794027
-45390 774477
408812 806877
32813 864956
-594379 939110
-400881 862851
-841240 825276
-623754 795456
-233265 84...

output:

1579

result:

ok 1 number(s): "1579"

Test #43:

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

input:

200
635384 485892
765764 574319
336258 334347
465048 520794
519375 558921
682283 607704
982737 801953
564318 664179
209807 405618
419262 582690
-7986 577806
-441678 673641
171933 603149
261948 582564
129839 653445
374771 807498
499641 893376
916239 999597
-190753 742980
162081 984042
-325008 701442
...

output:

1731

result:

ok 1 number(s): "1731"

Test #44:

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

input:

6
0 0
110828 157796
232685 157796
232685 331295
214662 305634
0 305634

output:

29

result:

ok 1 number(s): "29"

Test #45:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

10
0 0
110828 157796
233685 157796
233685 341295
232685 341295
232685 331295
214662 305634
-1000 305634
-1000 -10000
0 -10000

output:

49

result:

ok 1 number(s): "49"

Test #46:

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

input:

6
0 220492
-741872 220492
-750260 222985
-750260 205257
-690612 205257
0 0

output:

29

result:

ok 1 number(s): "29"

Test #47:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

10
0 -3000
10000 -3000
10000 220492
-741872 220492
-750260 222985
-750260 225985
-760260 225985
-760260 205257
-690612 205257
0 0

output:

49

result:

ok 1 number(s): "49"

Test #48:

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

input:

6
-999999 -1000000
1000000 999999
-999999 999999
-999999 -999999
-1000000 -999999
-1000000 -1000000

output:

25

result:

ok 1 number(s): "25"

Test #49:

score: 0
Accepted
time: 0ms
memory: 3328kb

input:

6
-999999 -1000000
-999999 -999999
1000000 -999999
1000000 999999
999998 999999
-1000000 -1000000

output:

17

result:

ok 1 number(s): "17"

Test #50:

score: 0
Accepted
time: 1ms
memory: 3336kb

input:

6
-999999 -1000000
-999998 -999999
1000000 -999999
1000000 999999
999998 999999
-1000000 -1000000

output:

33

result:

ok 1 number(s): "33"

Test #51:

score: 0
Accepted
time: 170ms
memory: 4816kb

input:

200
1000000 -999941
-999956 -999940
-998042 -997864
-998053 -997864
-994830 -994360
-994841 -994360
-990958 -990136
-990969 -990136
-983566 -982072
-983577 -982072
-978319 -976348
-978330 -976348
-976768 -974656
-976779 -974656
-975228 -972976
-975239 -972976
-973116 -970672
-973127 -970672
-972808 ...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #52:

score: 0
Accepted
time: 173ms
memory: 5028kb

input:

200
1000000 -998489
-999630 -998488
-992008 -959932
-992082 -959932
-989862 -948970
-989936 -948970
-989344 -946324
-989418 -946324
-978688 -891892
-978762 -891892
-967292 -833680
-967366 -833680
-966182 -828010
-966256 -828010
-965146 -822718
-965220 -822718
-964850 -821206
-964924 -821206
-964480 ...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #53:

score: 0
Accepted
time: 175ms
memory: 5056kb

input:

200
-1000000 999787
998030 999786
958630 978600
959024 978600
946810 972180
947204 972180
940112 968542
940506 968542
837278 912688
837672 912688
817972 902202
818366 902202
814426 900276
814820 900276
809698 897708
810092 897708
798272 891502
798666 891502
788028 885938
788422 885938
785270 884440
...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #54:

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

input:

200
-1000000 997586
999374 997585
897023 840127
897336 840127
789977 674941
790290 674941
783091 664315
783404 664315
759616 628090
759929 628090
708597 549361
708910 549361
704215 542599
704528 542599
702963 540667
703276 540667
700459 536803
700772 536803
699520 535354
699833 535354
624400 419434
...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #55:

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

input:

200
1000000 -999485
975920 -982198
965600 -974200
965256 -974200
964224 -973168
963880 -973168
962504 -971878
962160 -971878
961816 -971362
961472 -971362
961128 -970846
960784 -970846
948744 -961558
948400 -961558
931200 -948400
930856 -948400
906088 -929566
905744 -929566
881320 -910990
880976 -91...

output:

441250454

result:

ok 1 number(s): "441250454"

Test #56:

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

input:

200
1000000 -999175
975085 -976872
963760 -966134
963307 -966134
918460 -924834
918007 -924834
714157 -738571
713704 -738571
638959 -670013
638506 -670013
460477 -507291
460024 -507291
360364 -416018
359911 -416018
359458 -415192
359005 -415192
355381 -411475
354928 -411475
341338 -398672
340885 -39...

output:

441250454

result:

ok 1 number(s): "441250454"

Test #57:

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

input:

200
-1000000 998441
-996730 995710
-994441 992590
-994114 992590
-985285 981670
-984958 981670
-971878 965680
-971551 965680
-967627 960610
-967300 960610
-947026 936040
-946699 936040
-925771 910690
-925444 910690
-797587 757810
-797260 757810
-791374 750400
-791047 750400
-712240 656020
-711913 65...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #58:

score: 0
Accepted
time: 178ms
memory: 4888kb

input:

200
-1000000 998176
-999748 997810
-999496 996350
-999412 996350
-999160 994890
-999076 994890
-982360 921890
-982276 921890
-981352 917510
-981268 917510
-975136 890500
-975052 890500
-850144 347380
-850060 347380
-817216 204300
-817132 204300
-800920 133490
-800836 133490
-787816 76550
-787732 765...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #59:

score: 0
Accepted
time: 170ms
memory: 4876kb

input:

200
100000 -999633
239 -999632
3094 -999448
239 -999448
7467 -999264
239 -999264
4608 -998896
239 -998896
649 -998712
239 -998712
2980 -998528
239 -998528
1563 -998344
239 -998344
7731 -989788
239 -989788
744 -927504
239 -927504
2244 -838724
239 -838724
8203 -807628
239 -807628
4217 -780304
239 -780...

output:

441250450

result:

ok 1 number(s): "441250450"

Test #60:

score: 0
Accepted
time: 1ms
memory: 3388kb

input:

4
-899998 -900000
0 0
450000 450001
449998 449999

output:

7

result:

ok 1 number(s): "7"

Test #61:

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

input:

4
-1000000 -1000000
0 -1
999999 999997
-1 0

output:

7

result:

ok 1 number(s): "7"

Test #62:

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

input:

5
1000000 -1000000
1000000 999999
999999 0
999999 999998
-1000000 -1000000

output:

10

result:

ok 1 number(s): "10"

Test #63:

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

input:

10
-800000 -799999
199991 199997
799987 799996
999985 999995
599988 599996
199990 199996
-200006 -200002
-600003 -600001
-800001 -800000
-1000000 -1000000

output:

73

result:

ok 1 number(s): "73"

Test #64:

score: 0
Accepted
time: 105ms
memory: 4820kb

input:

200
-677343 996088
-731021 806109
-703638 644867
-694433 455591
-698504 132249
-745640 -209598
-859170 -239875
-874703 -116547
-922684 -350844
-920583 296332
-867486 433468
-860134 490879
-849686 -2551
-813758 684881
-777869 965896
-905744 958941
-983905 544305
-996951 494366
-982454 -386675
-977004...

output:

5283

result:

ok 1 number(s): "5283"

Test #65:

score: 0
Accepted
time: 114ms
memory: 4940kb

input:

191
2 3
2 2
1 2
0 1
3 2
5 4
5 3
4 2
6 2
8 4
9 4
9 5
8 5
7 4
7 6
6 5
6 3
5 5
4 4
3 4
5 6
6 6
6 7
8 9
7 9
3 5
2 5
4 7
2 6
1 6
1 7
2 7
2 8
1 10
2 9
1 11
3 9
4 10
3 10
2 11
3 11
3 12
1 12
1 13
3 13
1 14
1 15
2 14
3 15
4 15
3 14
4 13
6 13
4 14
5 14
7 13
6 14
8 13
8 12
4 12
4 11
9 11
7 10
5 10
3 8
3 7
5 9...

output:

55064

result:

ok 1 number(s): "55064"

Test #66:

score: 0
Accepted
time: 96ms
memory: 4848kb

input:

183
3 4
2 8
2 7
1 7
1 8
0 12
0 6
1 6
1 4
0 5
0 0
1 3
1 0
2 6
2 3
3 2
2 2
3 1
2 1
2 0
12 0
12 1
13 0
15 0
13 1
14 1
16 0
16 3
15 1
13 3
14 3
13 4
15 3
15 2
16 4
16 8
15 6
15 4
14 4
12 5
13 5
12 6
12 8
13 7
13 8
12 9
13 9
14 7
14 8
15 8
14 6
13 6
14 5
16 9
16 10
15 12
16 11
16 16
12 16
13 15
13 14
14 ...

output:

5564

result:

ok 1 number(s): "5564"

Test #67:

score: 0
Accepted
time: 120ms
memory: 4876kb

input:

195
14 11
13 11
13 10
14 9
14 7
15 10
15 8
14 6
13 7
13 9
12 11
12 12
11 12
11 13
10 12
10 13
9 14
9 12
8 14
7 15
6 15
8 13
7 13
8 12
7 11
8 10
8 9
6 12
7 12
6 13
4 14
6 14
5 15
8 16
5 16
4 15
4 16
0 16
0 15
3 15
1 14
1 13
0 14
0 11
1 12
1 9
2 8
1 8
0 10
0 2
1 2
2 1
0 1
0 0
12 0
10 1
11 1
10 2
7 2
6...

output:

8148

result:

ok 1 number(s): "8148"

Test #68:

score: 0
Accepted
time: 106ms
memory: 4844kb

input:

186
13 16
12 15
12 14
13 15
15 15
15 14
14 14
13 13
14 13
14 12
13 12
12 13
13 14
11 13
9 13
8 14
11 14
11 15
12 16
6 16
10 15
7 15
5 16
2 16
5 15
6 15
7 14
6 14
4 15
3 15
4 14
4 13
2 11
1 14
1 15
2 12
2 14
3 13
3 14
1 16
0 16
0 8
1 10
1 13
2 7
2 10
3 11
3 9
5 11
6 11
7 12
5 12
4 11
4 12
5 13
6 13
5...

output:

9369

result:

ok 1 number(s): "9369"

Test #69:

score: 0
Accepted
time: 3ms
memory: 3536kb

input:

38
1 95
2 94
2 129
1 96
1 152
2 130
2 156
1 153
1 165
2 157
2 174
1 173
1 189
2 175
2 190
1 190
1 195
2 191
2 199
1 199
1 196
0 199
0 159
1 172
1 166
0 158
0 47
1 83
1 45
0 46
0 0
2 0
2 4
1 1
1 44
2 5
2 93
1 84

output:

263261

result:

ok 1 number(s): "263261"

Test #70:

score: 0
Accepted
time: 6ms
memory: 3592kb

input:

57
192 0
170 1
188 1
193 0
195 0
189 1
198 1
196 0
199 0
199 2
164 2
169 1
152 1
163 2
115 2
117 1
106 1
114 2
82 2
105 1
93 1
81 2
62 2
49 1
41 1
61 2
5 2
25 1
11 1
4 2
0 2
0 1
6 1
0 0
4 0
7 1
10 1
5 0
17 0
26 1
40 1
18 0
55 0
50 1
73 1
56 0
97 0
74 1
92 1
98 0
127 0
118 1
128 0
153 0
119 1
151 1
1...

output:

134218614

result:

ok 1 number(s): "134218614"

Test #71:

score: 0
Accepted
time: 7ms
memory: 3588kb

input:

71
2 970
1 939
1 966
2 971
2 998
1 967
1 991
2 999
1 992
1 999
0 999
0 825
1 938
1 854
0 824
0 790
1 853
1 820
0 789
0 776
1 801
1 733
0 775
0 729
1 732
1 690
0 728
0 638
1 689
1 620
0 637
0 361
1 583
1 414
0 360
0 221
1 288
1 156
0 220
0 12
1 22
1 10
0 11
0 0
1 0
1 1
2 0
2 13
1 2
1 9
2 14
2 71
1 23...

output:

838862656

result:

ok 1 number(s): "838862656"

Test #72:

score: 0
Accepted
time: 15ms
memory: 3664kb

input:

80
427 0
435 1
495 1
428 0
467 0
496 1
553 1
468 0
566 0
554 1
655 1
567 0
748 0
656 1
740 1
749 0
797 0
741 1
761 1
798 0
887 0
762 1
825 1
888 0
926 0
826 1
891 1
927 0
965 0
892 1
951 1
966 0
999 0
970 1
999 1
999 2
986 2
969 1
952 1
985 2
492 2
434 1
354 1
491 2
293 2
353 1
217 1
292 2
161 2
216...

output:

445383386

result:

ok 1 number(s): "445383386"

Test #73:

score: 0
Accepted
time: 17ms
memory: 3684kb

input:

91
0 4
1 18
1 44
2 76
2 32
1 17
1 10
2 31
2 29
1 9
1 6
2 21
2 13
1 4
1 5
0 3
0 1
1 3
1 2
2 12
2 3
1 1
0 0
1 0
2 1
2 0
3 0
3 4
2 2
3 5
3 19
2 22
2 28
3 20
3 61
2 77
2 78
1 45
1 69
2 79
2 92
3 62
3 122
2 93
2 99
3 123
3 135
2 100
2 165
3 136
3 191
2 166
2 178
3 192
3 195
2 188
2 179
1 184
1 196
2 193
...

output:

688776

result:

ok 1 number(s): "688776"

Test #74:

score: 0
Accepted
time: 12ms
memory: 3516kb

input:

80
52 2
66 1
32 1
16 0
41 0
67 1
75 1
42 0
114 0
122 1
135 1
140 2
187 2
136 1
159 1
115 0
125 0
160 1
166 1
126 0
196 0
186 1
195 1
195 2
196 1
197 1
197 0
199 0
198 1
199 1
199 2
198 2
199 3
196 3
197 2
196 2
195 3
194 3
189 2
194 2
185 1
167 1
188 2
193 3
133 3
139 2
131 2
132 3
20 3
80 2
130 2
1...

output:

3019

result:

ok 1 number(s): "3019"

Test #75:

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

input:

142
3 368
2 351
2 420
3 369
3 459
2 421
2 446
3 460
3 469
2 447
2 465
1 447
1 487
2 468
2 466
3 470
3 512
2 469
2 515
3 513
3 616
2 516
2 564
3 617
3 625
2 565
2 591
3 626
3 635
2 592
2 607
3 636
3 717
2 658
2 635
1 656
1 693
2 717
2 659
3 718
3 742
2 731
2 718
1 694
1 739
2 735
2 732
3 743
3 749
2 ...

output:

128369

result:

ok 1 number(s): "128369"

Test #76:

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

input:

134
552 1
527 0
702 0
633 1
679 1
703 0
714 0
680 1
700 1
699 2
716 2
722 1
701 1
715 0
734 0
736 1
737 1
735 0
739 0
738 1
743 1
740 0
749 0
744 1
749 1
749 3
746 3
748 2
746 2
745 3
744 3
745 2
741 2
735 1
723 1
720 2
740 2
743 3
737 3
719 2
717 2
736 3
680 3
698 2
663 2
679 3
631 3
662 2
605 2
63...

output:

334697

result:

ok 1 number(s): "334697"

Test #77:

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

input:

20
0 0
10 0
10 10
9 10
9 9
8 9
8 10
7 10
7 7
6 7
6 10
5 10
5 5
4 5
4 10
3 10
3 3
2 3
2 10
0 10

output:

199

result:

ok 1 number(s): "199"

Test #78:

score: 0
Accepted
time: 117ms
memory: 4888kb

input:

200
0 0
100 0
100 100
99 100
99 99
98 99
98 100
97 100
97 97
96 97
96 100
95 100
95 95
94 95
94 100
93 100
93 93
92 93
92 100
91 100
91 91
90 91
90 100
89 100
89 89
88 89
88 100
87 100
87 87
86 87
86 100
85 100
85 85
84 85
84 100
83 100
83 83
82 83
82 100
81 100
81 81
80 81
80 100
79 100
79 79
78 79...

output:

263924743

result:

ok 1 number(s): "263924743"

Test #79:

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

input:

26
0 0
5 3
6 2
20 11
20 12
25 15
27 14
40 23
40 24
45 27
50 26
60 30
59 36
55 33
50 30
48 32
35 22
35 21
30 18
26 20
15 10
15 9
10 6
8 7
-3 2
0 -1

output:

4349

result:

ok 1 number(s): "4349"

Test #80:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

8
0 0
20 -10
40 0
40 5
60 0
60 -5
80 0
40 20

output:

39

result:

ok 1 number(s): "39"

Test #81:

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

input:

10
0 0
20 -10
40 0
45 0
40 5
60 0
65 0
60 -5
80 0
40 20

output:

61

result:

ok 1 number(s): "61"

Test #82:

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

input:

4
0 0
50 -20
100 0
50 20

output:

11

result:

ok 1 number(s): "11"

Test #83:

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

input:

8
0 0
0 10
-10 0
50 -20
110 0
100 10
100 0
50 -10

output:

27

result:

ok 1 number(s): "27"