QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#118110#5443. Security at Museumshos_lyricAC ✓30ms4964kbC++149.2kb2023-07-03 03:46:292023-07-03 03:46:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-03 03:46:47]
  • 评测
  • 测评结果:AC
  • 用时:30ms
  • 内存:4964kb
  • [2023-07-03 03:46:29]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;


struct Pt {
  Int x, y;
  Pt() {}
  Pt(Int x_, Int y_) : x(x_), y(y_) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
  Int abs2() const { return x * x + y * y; }
  Int dot(const Pt &a) const { return x * a.x + y * a.y; }
  Int det(const Pt &a) const { return x * a.y - y * a.x; }
  bool operator==(const Pt &a) const { return (x == a.x && y == a.y); }
  bool operator!=(const Pt &a) const { return !(*this == a); }
  bool operator<(const Pt &a) const { return (x < a.x || (x == a.x && y < a.y)); }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
int sig(Int r) { return (r < 0) ? -1 : (r > 0) ? +1 : 0; }
Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }

int cmpArg(const Pt &a, const Pt &b) {
  const int sa = (a.y > 0) ? 1 : (a.y < 0) ? 3 : (a.x > 0) ? 0 : 2;
  const int sb = (b.y > 0) ? 1 : (b.y < 0) ? 3 : (b.x > 0) ? 0 : 2;
  return (sa < sb) ? -1 : (sa > sb) ? +1 : sig(b.det(a));
}

// Watch out for the case a == b.
int iSP(const Pt &a, const Pt &b, const Pt &c) {
  int s = sig((b - a).det(c - a));
  if (s) return s;
  if (sig((b - a).dot(c - a)) < 0) return -2; // c-a-b
  if (sig((a - b).dot(c - b)) < 0) return +2; //   a-b-c
  return 0;
}

// intersection = a + (numer/denom) (b - a)
pair<Int, Int> pLLRate(const Pt &a, const Pt &b, const Pt &c, const Pt &d) {
  const Pt ab = b - a, cd = d - c;
  return make_pair((c - a).det(cd), ab.det(cd));
}

bool insideWeaklyGS(const vector<Pt> &ps, const Pt &a, const Pt &b) {
  const int psLen = ps.size();
  assert(psLen >= 3);
  assert(a != b);
  const Pt ab = b - a;
  // number of intersections of ps (enlarged) and ray a-b
  int cnt = 0;
  for (int i = 0; i < psLen; ++i) {
    const Pt &p0 = ps[i];
    const Pt &p1 = ps[(i + 1 >= psLen) ? (i + 1 - psLen) : (i + 1)];
    const Pt &p2 = ps[(i + 2 >= psLen) ? (i + 2 - psLen) : (i + 2)];
    const int s0 = sig(tri(a, b, p0));
    const int s1 = sig(tri(a, b, p1));
    // in p0-p1
    if (s0 * s1 < 0) {
      const auto res = pLLRate(a, b, p0, p1);
      const Int numer = (res.second < 0) ? -res.first : res.first;
      const Int denom = (res.second < 0) ? -res.second : res.second;
      if (numer <= 0) {
      } else if (numer >= denom) {
        ++cnt;
      } else {
        return false;
      }
    }
    // at p1
    if (s1 == 0) {
      const int s2 = sig(tri(a, b, p2));
      if (s0 * s2 < 0 || (s0 != s2 && sig(tri(p0, p1, p2)) > 0)) {
        const Int numer = ab.dot(p1 - a);
        const Int denom = ab.abs2();
        if (numer <= 0) {
        } else if (numer >= denom) {
          ++cnt;
        } else {
          return false;
        }
      }
    }
  }
  return (cnt % 2 != 0);
}


int N;
vector<Pt> P;

bool can[210][210];
Mint dp[210][210];

int main() {
  for (; ~scanf("%d", &N); ) {
    P.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld%lld", &P[i].x, &P[i].y);
    }
// for(int i=0;i<N;++i){for(int j=0;j<N;++j)cerr<<((i==j)?2:insideWeaklyGS(P,P[i],P[j]))<<" ";cerr<<endl;}
    
    memset(can, 0, sizeof(can));
    for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j) {
      if (insideWeaklyGS(P, P[i], P[j])) {
        can[i][j] = can[j][i] = true;
      }
    }
    using Dir = pair<Pt, pair<int, int>>;
    vector<Dir> dirs;
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (can[i][j]) {
      dirs.emplace_back(P[j] - P[i], make_pair(i, j));
    }
    const int dirsLen = dirs.size();
    sort(dirs.begin(), dirs.end(), [&](const Dir &d0, const Dir &d1) -> bool {
      return (cmpArg(d0.first, d1.first) < 0);
    });
    
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < N; ++i) {
      dp[i][i] = 1;
    }
    for (int a = 0, b; a < dirsLen; a = b) {
      for (b = a + 1; b < dirsLen && cmpArg(dirs[a].first, dirs[b].first) == 0; ++b) {}
      const Pt vec = dirs[a].first;
      sort(dirs.begin() + a, dirs.begin() + b, [&](const Dir &d0, const Dir &d1) -> bool {
        return (vec.dot(P[d0.second.first]) < vec.dot(P[d1.second.first]));
      });
// pv(dirs.begin()+a,dirs.begin()+b);
      for (int c = a; c < b; ++c) {
        for (int i = 0; i < N; ++i) {
          dp[i][dirs[c].second.second] += dp[i][dirs[c].second.first];
        }
      }
    }
    
    Mint ans = 0;
    for (int i = 0; i < N; ++i) {
      ans += dp[i][i];
    }
    // 1 point
    ans -= N;
    // collinear
    for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j) if (can[i][j]) {
      int cnt = 0;
      for (int k = 0; k < N; ++k) if (i != k && j != k) {
        if (iSP(P[i], P[j], P[k]) == 0) {
          ++cnt;
        }
      }
      ans -= Mint(4).pow(cnt);
      ans += Mint(2).pow(cnt);
    }
    
    printf("%u\n", ans.x);
  }
  return 0;
}

詳細信息

Test #1:

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

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: 1ms
memory: 3864kb

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

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: 3860kb

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: 3868kb

input:

4
0 0
10 5
20 0
10 10

output:

7

result:

ok 1 number(s): "7"

Test #8:

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

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #10:

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

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

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

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

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: 1ms
memory: 3848kb

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: 1ms
memory: 3904kb

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: 1ms
memory: 3868kb

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: 1ms
memory: 3796kb

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: 1ms
memory: 3788kb

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: 1ms
memory: 3800kb

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: 1ms
memory: 3792kb

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: 3832kb

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: 0ms
memory: 3864kb

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: 3864kb

input:

3
1000000 -1000000
1000000 1000000
-1000000 -1000000

output:

4

result:

ok 1 number(s): "4"

Test #23:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #24:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #25:

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

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: 30ms
memory: 4964kb

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: 14ms
memory: 3996kb

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: 19ms
memory: 4252kb

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: 1ms
memory: 3788kb

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: 1ms
memory: 3796kb

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: 1ms
memory: 3904kb

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: 1ms
memory: 3860kb

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: 0ms
memory: 3792kb

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: 6ms
memory: 3928kb

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: 6ms
memory: 3936kb

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: 7ms
memory: 3936kb

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: 6ms
memory: 3936kb

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: 3ms
memory: 3944kb

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: 6ms
memory: 3932kb

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: 6ms
memory: 4000kb

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: 6ms
memory: 4000kb

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: 3ms
memory: 3984kb

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: 7ms
memory: 3932kb

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: 1ms
memory: 3880kb

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: 1ms
memory: 3912kb

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: 0ms
memory: 3820kb

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: 0ms
memory: 3872kb

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: 1ms
memory: 3832kb

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: 3868kb

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: 3928kb

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: 14ms
memory: 3992kb

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: 14ms
memory: 4008kb

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: 14ms
memory: 4056kb

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: 10ms
memory: 3988kb

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: 14ms
memory: 4084kb

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: 14ms
memory: 3920kb

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: 14ms
memory: 3988kb

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: 14ms
memory: 3992kb

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: 13ms
memory: 3920kb

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: 3904kb

input:

4
-899998 -900000
0 0
450000 450001
449998 449999

output:

7

result:

ok 1 number(s): "7"

Test #61:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #62:

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

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: 0ms
memory: 3928kb

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: 7ms
memory: 3948kb

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: 6ms
memory: 3884kb

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: 6ms
memory: 3944kb

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: 7ms
memory: 3952kb

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: 3ms
memory: 3956kb

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: 1ms
memory: 3880kb

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: 2ms
memory: 3880kb

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: 2ms
memory: 3916kb

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: 2ms
memory: 3960kb

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: 2ms
memory: 3936kb

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: 2ms
memory: 3948kb

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: 3ms
memory: 3936kb

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: 3ms
memory: 3944kb

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: 1ms
memory: 3864kb

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: 8ms
memory: 4040kb

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: 1ms
memory: 3964kb

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: 1ms
memory: 3908kb

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: 0ms
memory: 3832kb

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: 1ms
memory: 3956kb

input:

4
0 0
50 -20
100 0
50 20

output:

11

result:

ok 1 number(s): "11"

Test #83:

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

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"