QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#760030#5079. Empty Quadrilateralsgugugaga#AC ✓1833ms3792kbC++2013.1kb2024-11-18 14:12:262024-11-18 14:12:32

Judging History

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

  • [2024-11-18 14:12:32]
  • 评测
  • 测评结果:AC
  • 用时:1833ms
  • 内存:3792kb
  • [2024-11-18 14:12:26]
  • 提交

answer

/*************************************
*    author: marvinthang             *
*    created: 18.11.2024 11:47:59    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define             fi  first
#define             se  second
#define           left  ___left___
#define          right  ___right___
#define   scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define  print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
    #include "debug.h"
#else
    #define DB(...)
    #define db(...) ""
    #define debug(...)
#endif

namespace std {
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; }
template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; }
template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; }
template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {} template <class...Args> decltype(auto)operator()(Args &&...args) { return fun_(ref(*this), forward<Args>(args)...); } };
template <class Fun> decltype(auto)y_combinator(Fun &&fun) { return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun)); }
template <typename T, int D> struct Vec: public vector <Vec<T, D - 1>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template <typename ...Args> Vec(int n = 0, Args ...args): vector <Vec<T, D - 1>>(n, Vec<T, D - 1>(args...)) {} };
template <typename T> struct Vec<T, 1>: public vector<T>{ Vec(int n = 0, const T &val = T()): vector<T>(n, val) {} };
#if __cplusplus < 202002L
    template <class T> int ssize(const T &a) { return a.size(); }
#endif
}

struct Point {
    long long x, y;
    Point(long long x = 0, long long y = 0): x(x), y(y) {}
    friend scan_op(Point) { return in >> u.x >> u.y; }
    friend print_op(Point) { return out << make_pair(u.x, u.y); }
    bool operator == (const Point &other) const { return x == other.x && y == other.y; }
    bool operator < (const Point &other) const { return make_pair(x, y) < make_pair(other.x, other.y); }
    Point & operator += (const Point &other) {x += other.x; y += other.y; return *this; }
    Point & operator -= (const Point &other) { x -= other.x; y -= other.y; return *this; }
    Point & operator *= (long long v) { x *= v; y *= v; return *this; }
    Point & operator /= (long long v) { x /= v; y /= v; return *this; }
    Point operator + (const Point &other) const { return Point(*this) += other; }
    Point operator - (const Point &other) const { return Point(*this) -= other; }
    Point operator * (long long v) const { return Point(*this) *= v; }
    Point operator / (long long v) const { return Point(*this) /= v; }
    long long dot(const Point &other) const { return x * other.x + y * other.y; }
    long long cross(const Point &other) const { return x * other.y - y * other.x; }
    long long norm(void) const { return x * x + y * y; }
    double length(void) const { return sqrtl(norm()); }
    double angle(const Point &other) const { return acos(dot(other) / length() / other.length()); }
    long long cross(const Point &a, const Point &b) const { return (a - *this).cross(b - *this); }
};
int sgn(long long val) { return val < 0 ? -1 : !!val; }
int ccw(const Point &a, const Point &b, const Point &c) { return sgn(a.cross(b, c)); }
double linePointDist(const Point &a, const Point &b, const Point &c, bool isSegment) {
    double dist = abs((b - a).cross(c - a)) / (a - b).length();
    if (isSegment) {
        if ((a - b).dot(c - b) < 0) return (b - c).length();
        if ((b - a).dot(c - a) < 0) return (a - c).length();
    }
    return dist;
}
bool inter1(long long a, long long b, long long c, long long d) {
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    return max(a, c) <= min(b, d);
}
bool check_inter(const Point &a, const Point &b, const Point &p) {
    return !a.cross(b, p) && inter1(a.x, b.x, p.x, p.x) && inter1(a.y, b.y, p.y, p.y);
}
bool check_inter(const Point &a, const Point &b, const Point &c, const Point &d) {
    if (!c.cross(a, d) && !c.cross(b, d)) 
        return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y);
    return ccw(a, b, c) != ccw(a, b, d) && ccw(c, d, a) != ccw(c, d, b);
}
struct Line {
    // ax + by = c
    long long a, b, c;
    Line(long long a = 0, long long b = 0, long long c = 0): a(a), b(b), c(c) {}
    Line(const Point &m, const Point &n) {
        a = m.y - n.y;
        b = n.x - m.x;
        c = a * m.x + b * m.y;
    }
    bool intersect(const Line &other, Point &res) const {
        long long x = a * other.b - b * other.a;
        if (!x) return false;
        res.x = (other.b * c - b * other.c) / x;
        res.y = (a * other.c - c * other.a) / x;
        return true;
    }
    bool parallel(const Line &other) const {
        return a * other.b - b * other.a == 0;
    }
    bool equivalent(const Line &other) const {
        return a * other.b - b * other.a == 0
            && a * other.c - c * other.a == 0
            && b * other.c - c * other.b == 0;
    }
};
void convex_hull(vector <Point> &p) {
    if (p.size() <= 1) return;
    sort(p.begin(), p.end());
    Point p1 = p[0], p2 = p.back();
    vector <Point> up {p1}, down {p1};
    for (int i = 1; i < (int) p.size(); ++i) {
        int c = ccw(p1, p[i], p2);
        if (i == (int) p.size() - 1 || c < 0) {
            while (up.size() > 1 && ccw(up.end()[-2], up.back(), p[i]) >= 0) up.pop_back();
            up.push_back(p[i]);
        }
        if (i == (int) p.size() - 1 || c > 0) {
            while (down.size() > 1 && ccw(down.end()[-2], down.back(), p[i]) <= 0) down.pop_back();
            down.push_back(p[i]);
        }
    }
    p = move(up);
    p.insert(p.end(), down.rbegin() + 1, down.rend() - 1);
    if (p.size() == 2 && p[0] == p[1]) p.pop_back();
}
long long area_x2(const vector <Point> &p) {
    long long res = 0;
    for (int i = 0; i < (int) p.size(); ++i) res += p[i].cross(p[i == (int) p.size() - 1 ? 0 : i + 1]);
    return abs(res);
}

template<
    class T,        // data type for nodes
    T (*op) (const T&, const T&), // operator to combine 2 nodes
    T (*e)()        // identity element
    >
struct SegTree {
    SegTree(): SegTree(0) {}
    SegTree(int n) : SegTree(vector<T>(n, e())) {}
    SegTree(const vector <T>& v) : n(v.size()) {
        log = 0;
        while ((1 << log) < n) ++log;
        size = 1 << log;
        d = vector<T>(size << 1, e());
        for (int i = 0; i < n; ++i) d[size + i] = v[i];
        for (int i = size - 1; i > 0; --i) update(i);
    }

    // 0 <= p < n
    void set(int p, T x) {
        assert(0 <= p && p < n);
        p += size; d[p] = x;
        for (int i = 1; i <= log; ++i) update(p >> i);
    }

    // 0 <= p < n
    T get(int p) const {
        assert(0 <= p && p < n);
        return d[p + size];
    }

    // Get product in range [l, r-1]
    // 0 <= l <= r <= n
    // For empty segment (l == r) -> return e()
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        T sml = e(), smr = e();
        l += size; r += size;
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1; r >>= 1;
        }
        return op(sml, smr);
    }

    T all_prod() const { return d[1]; }

    // Binary search on SegTree to find largest r:
    //	f(op(a[l] .. a[r-1])) = true   (assuming empty array is always true)
    //	f(op(a[l] .. a[r])) = false	(assuming op(..., a[n]), which is out of bound, is always false)
    template <bool (*f)(T)> int max_right(int l) const { return max_right(l, [](T x) { return f(x); }); }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= n);
        assert(f(e()));
        if (l == n) return n;
        l += size;
        T sm = e();
        do {
            while (!(l & 1)) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = l << 1;
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    // Binary search on SegTree to find smallest l:
    //	f(op(a[l] .. a[r-1])) = true	  (assuming empty array is always true)
    //	f(op(a[l-1] .. a[r-1])) = false   (assuming op(a[-1], ..), which is out of bound, is always false)
    template <bool (*f)(T)> int min_left(int r) const { return min_left(r, [](T x) { return f(x); }); }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        T sm = e();
        do {
            r--;
            while (r > 1 && (r & 1)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = r << 1 | 1;
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int n, size, log;
    vector <T> d;
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
pair <short, short> op(const pair <short, short> &a, const pair <short, short> &b) {
    return pair{max(a.fi, b.fi), min(a.se, b.se)};
}
pair <short, short> e() { return pair{-1, 1000}; }

void process(void) {
    short n; cin >> n;
    vector <Point> p(n); cin >> p;
    long long res = 0;
    vector <short> pos_a(n), pos_b(n);
    SegTree <pair <short, short>, op, e> st(n);
    for (short i = 0; i < n; ++i) {
        for (short j = 0; j < i; ++j) {
            Point s = p[i], t = p[j];
            vector <short> left, right;
            for (short k = 0; k < n; ++k) if (k != i && k != j) {
                (ccw(s, t, p[k]) > 0 ? left : right).push_back(k);
            }
            auto solve = [&] (auto &a) {
                sort(a.begin(), a.end(), [&] (const short &a, const short &b) {
                    return ccw(t, p[a], p[b]) > 0;
                });
                auto b = a;
                sort(b.begin(), b.end(), [&] (const short &a, const short &b) {
                    return ccw(s, p[a], p[b]) > 0;
                });
                for (short i = 0; i < ssize(b); ++i) {
                    pos_a[a[i]] = i;
                    pos_b[b[i]] = i;
                }
                vector <pair <short, short>> val(ssize(b));
                for (short i = 0; i < ssize(b); ++i) {
                    val[i] = pair{i, pos_a[b[i]]};
                }
                st = SegTree <pair <short, short>, op, e>(val);
                short ta = 0, tb = 0;
                for (auto i: a) {
                    st.set(pos_b[i], e());
                    auto val = st.prod(0, pos_b[i]);
                    if (val.fi == -1) ++ta;
                    else {
                        if (b[val.fi] == a[val.se]) ++tb;
                    }
                }
                return pair{ta, tb};
            };
            auto [la, lb] = solve(left);
            swap(s, t);
            auto [ra, rb] = solve(right);
            res += (int) la * ra + lb + rb;
        }
    }
    cout << res / 2 << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    file("test");
    // int t; cin >> t; while (t--)
    process();
    return (0^0);
}

詳細信息

Test #1:

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

input:

5
0 0
2 4
6 2
6 -2
7 3

output:

8

result:

ok single line: '8'

Test #2:

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

input:

4
0 0
10 0
5 10
3 2

output:

3

result:

ok single line: '3'

Test #3:

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

input:

10
10 10
1 0
4 8
-1 -4
-7 -4
-3 2
5 -10
-10 -5
1 1
5 -3

output:

170

result:

ok single line: '170'

Test #4:

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

input:

1
0 0

output:

0

result:

ok single line: '0'

Test #5:

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

input:

2
0 0
1 0

output:

0

result:

ok single line: '0'

Test #6:

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

input:

3
0 0
1 0
10 10

output:

0

result:

ok single line: '0'

Test #7:

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

input:

4
0 0
1 0
1 1
0 1

output:

1

result:

ok single line: '1'

Test #8:

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

input:

4
-1000000000 1000000000
1000000000 1000000000
1000000000 -1000000000
-1000000000 -1000000000

output:

1

result:

ok single line: '1'

Test #9:

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

input:

4
-8 -3
1 1
7 0
-10 1

output:

1

result:

ok single line: '1'

Test #10:

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

input:

5
-5 8
-7 6
8 9
-8 -7
3 1

output:

5

result:

ok single line: '5'

Test #11:

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

input:

10
-82 -34
9 -90
-67 13
80 -31
-45 51
28 90
-90 -75
58 33
-12 71
90 -80

output:

210

result:

ok single line: '210'

Test #12:

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

input:

100
3759 9658
2910 -9943
4170 9478
-7675 -6575
-6661 7820
6123 8295
9859 -498
9799 42
-2324 -9578
-6860 7649
2269 -9996
8777 4515
8363 5630
6479 8015
-9991 -1944
8574 -7477
8687 -7393
7206 7266
5208 8983
-9081 -4460
-4262 9116
9722 651
9881 -5725
-4899 8911
9867 -592
-7206 7053
-3828 -9346
7471 6976...

output:

3921225

result:

ok single line: '3921225'

Test #13:

score: 0
Accepted
time: 323ms
memory: 3612kb

input:

203
-980345 -265686
-146271 -978033
917841 -441678
-916267 446738
-928177 -428655
850137 -573235
-525140 -879110
-563115 -865718
19693 999740
-304353 -948387
287100 -986973
-329294 -941062
936446 -395687
-933810 -415914
-27770 -989661
120040 -999643
899311 -480711
793647 625727
999790 7708
991740 -1...

output:

68685050

result:

ok single line: '68685050'

Test #14:

score: 0
Accepted
time: 1219ms
memory: 3548kb

input:

300
-109565666 -999084112
987010217 283882659
902175413 602257050
-649185052 919125832
776751215 -617742367
-997974804 287676067
-880568072 -587807228
-537465923 -936971665
-75548128 -997577354
-43885301 997630537
155312299 -972230096
-882508267 -583190585
-562836073 946534352
14128786 994305968
591...

output:

330791175

result:

ok single line: '330791175'

Test #15:

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

input:

4
-1 0
0 1
0 0
1 -1

output:

3

result:

ok single line: '3'

Test #16:

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

input:

4
-1000000 0
0 1000000
0 0
1000000 -1000000

output:

3

result:

ok single line: '3'

Test #17:

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

input:

5
-6 3
4 0
0 0
1 3
0 -1

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
-1 -2
1 0
3 1
5 0
1 4

output:

9

result:

ok single line: '9'

Test #19:

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

input:

6
0 -4
2 4
8 -1
-2 0
6 -2
5 -3

output:

18

result:

ok single line: '18'

Test #20:

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

input:

6
0 -4
2 4
8 -1
-2 0
6 -1
5 -3

output:

19

result:

ok single line: '19'

Test #21:

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

input:

6
0 -4
2 4
8 -1
-2 0
1 -1
5 -3

output:

20

result:

ok single line: '20'

Test #22:

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

input:

6
0 5
5 5
5 0
1 2
4 3
0 0

output:

22

result:

ok single line: '22'

Test #23:

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

input:

7
-63 100
51 -100
100 50
50 92
44 -96
0 90
-100 36

output:

37

result:

ok single line: '37'

Test #24:

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

input:

7
-63 100
51 -100
100 50
50 92
44 -96
40 80
-100 36

output:

38

result:

ok single line: '38'

Test #25:

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

input:

7
-63 100
51 -100
100 50
50 92
44 -96
0 0
-100 36

output:

39

result:

ok single line: '39'

Test #26:

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

input:

7
0 -40
20 40
80 -10
-20 00
60 -20
0 0
50 -30

output:

40

result:

ok single line: '40'

Test #27:

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

input:

7
0 -40
20 40
80 -10
-20 00
60 -10
0 0
50 -30

output:

42

result:

ok single line: '42'

Test #28:

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

input:

7
0 -40
20 40
80 -10
-20 00
60 -10
20 0
50 -30

output:

42

result:

ok single line: '42'

Test #29:

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

input:

7
0 -40
20 40
80 -10
-20 00
10 -10
20 0
50 -30

output:

40

result:

ok single line: '40'

Test #30:

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

input:

7
0 -40
20 40
80 -10
-20 00
40 -10
0 0
50 -30

output:

42

result:

ok single line: '42'

Test #31:

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

input:

7
-20 30
40 -10
50 30
20 20
40 10
30 0
80 0

output:

42

result:

ok single line: '42'

Test #32:

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

input:

9
-1000000 1000000
1000000 1000000
1000000 -1000000
-1000000 -1000000
-1 -2
1 0
3 1
5 0
1 4

output:

113

result:

ok single line: '113'

Test #33:

score: 0
Accepted
time: 1637ms
memory: 3780kb

input:

300
0 -40
20 40
80 -10
-20 00
60 -20
0 0
50 -30
3759 9658
2910 -9943
4170 9478
-7675 -6575
-6661 7820
6123 8295
9859 -498
9799 42
-2324 -9578
-6860 7649
2269 -9996
8777 4515
8363 5630
6479 8015
-9991 -1944
8574 -7477
8687 -7393
7206 7266
5208 8983
-9081 -4460
-4262 9116
9722 651
9881 -5725
-4899 891...

output:

48777998

result:

ok single line: '48777998'

Test #34:

score: 0
Accepted
time: 1645ms
memory: 3520kb

input:

300
-63 100
51 -100
100 50
50 92
44 -96
0 0
-100 36
3759 9658
2910 -9943
4170 9478
-7675 -6575
-6661 7820
6123 8295
9859 -498
9799 42
-2324 -9578
-6860 7649
2269 -9996
8777 4515
8363 5630
6479 8015
-9991 -1944
8574 -7477
8687 -7393
7206 7266
5208 8983
-9081 -4460
-4262 9116
9722 651
9881 -5725
-4899...

output:

45037874

result:

ok single line: '45037874'

Test #35:

score: 0
Accepted
time: 462ms
memory: 3632kb

input:

200
7006 -177
3756 -39
9872 -2618
8860 -8435
8567 -8858
3007 -9855
6431 -78
9573 -1996
645 -7499
3665 -9945
8083 -9316
4098 -11
8951 -1249
5575 -9951
8726 -1037
537 -1720
5520 -9957
9963 -4363
2960 -124
2250 -218
129 -5825
2687 -9786
6657 -9789
4055 -9977
9876 -5238
1496 -746
1577 -8771
2099 -290
12...

output:

9540323

result:

ok single line: '9540323'

Test #36:

score: 0
Accepted
time: 1828ms
memory: 3648kb

input:

300
-501908338 -342208696
-10167056 -346610906
-674262068 -513861820
740719799 -20856381
668020647 118853908
-594640750 -576677796
300321882 646151426
-253013235 593016512
902927188 793410806
-301044865 318724915
-486058015 -496110017
-351177263 -743387574
807088372 54542457
208214529 -524493165
-69...

output:

2795836

result:

ok single line: '2795836'

Test #37:

score: 0
Accepted
time: 1833ms
memory: 3596kb

input:

300
-482422458 -650575249
739358757 -239520925
-788783744 -570062901
-418837911 -745067752
423436230 819110878
841974335 -613836194
-768284217 720559856
-358549450 -256316335
291277639 -897729580
-110268594 -700475931
175686758 -367088054
-530875306 258552250
-212148201 -472842853
503829688 -1360053...

output:

2814628

result:

ok single line: '2814628'

Test #38:

score: 0
Accepted
time: 1830ms
memory: 3660kb

input:

300
356181715 89939368
-72443051 -704507906
-690966591 -279739694
-976538108 -341475796
93551668 -148779235
251274485 -116441701
849551224 -933105925
221551672 -277806162
411595935 -508423498
-490878234 -526198472
901722131 -943273082
-34626519 -349420547
664149659 -282364112
188299626 -41569992
-51...

output:

2708850

result:

ok single line: '2708850'

Test #39:

score: 0
Accepted
time: 1825ms
memory: 3780kb

input:

300
31840392 166106964
358911007 869126535
-621777650 -300184792
-67883155 -75407554
322946753 327310839
278025305 248174787
-126604649 -128856871
726704839 641989969
-321890281 428431976
-4185200 870480695
65151553 948684572
157543013 327022326
-432953230 59313390
130872597 499753387
186866250 7853...

output:

2745119

result:

ok single line: '2745119'

Test #40:

score: 0
Accepted
time: 1829ms
memory: 3656kb

input:

300
-4385121 -503122347
734999363 642635536
515185589 -470338969
375650132 185233124
477179262 101130709
1000000000 1000000000
347997647 -1000000000
-660477475 -261237081
920751336 820224292
524777849 -49304657
580674293 -194540800
748256112 384808467
112178604 145725198
310736009 -631543545
6096309...

output:

2698071

result:

ok single line: '2698071'

Test #41:

score: 0
Accepted
time: 1831ms
memory: 3520kb

input:

300
203045772 308711983
-916118373 318797670
-41260195 -986552053
637476708 950931779
-528765585 -353147471
990296819 98284627
-699115850 782110838
890436583 703447789
-229547159 -709125382
975139869 169993037
509469330 110669354
-675216600 637346207
-953801852 327918372
-22772314 -249145451
9276083...

output:

2796264

result:

ok single line: '2796264'

Test #42:

score: 0
Accepted
time: 1813ms
memory: 3776kb

input:

300
-944766581 480214191
-248842272 -753277593
-448997872 -482488443
-996752701 -260550745
-204818531 281299141
233897455 758175732
688878436 765531134
-823381320 -303603411
403496227 89922133
-357366993 320790475
-1000000000 -59389753
-658015306 826763677
538496279 900395547
703071549 677054086
-45...

output:

3509126

result:

ok single line: '3509126'

Test #43:

score: 0
Accepted
time: 1779ms
memory: 3656kb

input:

300
-182831980 -969196441
414272271 951848039
-548245229 -783948441
801132021 -563171314
-345329194 -598054683
-305508089 -924826054
-218220807 -526211105
-461925755 -713550422
507769882 -860203633
-47508636 999965834
653109611 -727477703
-269444125 -940959595
-230881125 -955536641
569600375 5562516...

output:

4762046

result:

ok single line: '4762046'

Test #44:

score: 0
Accepted
time: 1704ms
memory: 3644kb

input:

300
-771154090 780208833
-885146379 618774890
-929480005 524450406
988987341 -251030240
-528198190 935166148
916434667 495090115
-971988142 -123463555
927578054 473068874
-296540818 995693336
-974419944 401991872
-286359667 -324153147
-434454895 963693999
960637514 -395444073
789192595 -780327590
18...

output:

9910427

result:

ok single line: '9910427'

Test #45:

score: 0
Accepted
time: 1532ms
memory: 3544kb

input:

300
771496631 -715636432
-284370823 -992031886
221646111 -984376736
-502926656 942054170
957030786 250826089
-724998045 856842554
477328838 -923763580
-186630182 990308507
-996566153 -79000362
-997774710 161151873
330239361 976675527
-927892928 -428119195
975961758 153079132
880348453 495048261
6464...

output:

45124100

result:

ok single line: '45124100'

Test #46:

score: 0
Accepted
time: 1414ms
memory: 3636kb

input:

300
-999157963 -18189049
495673938 -900812371
695856806 879843169
-646890746 843856158
-607964011 -861384114
-642823118 846244239
-843220933 678715057
999228694 348303755
-866562377 -584734435
-987109903 -216026832
1000000000 336971228
-758379032 -733372125
-407150315 945513929
969993871 485721162
8...

output:

146429294

result:

ok single line: '146429294'

Test #47:

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

input:

300
-884798186 738312829
-878931221 747555150
-975559797 -87153305
90984653 986432102
948135107 239847165
-972411704 479962936
-457628206 -898161096
189527452 965324546
685266767 -798324643
702689516 701905705
726151515 -764601703
-951644487 -184972102
770505738 609751583
296791271 934118777
8649066...

output:

262517341

result:

ok single line: '262517341'