2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest

A 問題

尺取法をベースに解法を設計した。等差側とそうでない側、それぞれ p, q を尺取ポインタとして、うまく２つを動かしていく。もし \( ap+d < t_q \) なら、\(ap,a(p+1),a(p+2),\ldots\) をまとめて取れば良い。そうでないときは愚直にすすめる。

実装の工夫としては、m 側に番兵を設置し条件を緩やかにした。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

int main() {
  long long n, m, a, d;
  cin >> n >> m >> a >> d;

  vector<long long> t(m + 1);
  for (int i = 0; i < m; i++) {
    scanf("%lld", &t[i]);
  }
  m++;
  t.back() = 4e18;

  long long cnt = d / a + 1;

  long long p = 1;
  long long q = 0;

  long long ans = 0;
  while (p <= n) {
    if (a*p + d < t[q]) {
      long long k = (t[q] - 1 - a*p - d) / (cnt*a) + 1;
      k = min(k, (n - p)/cnt + 1);
      ans += k;
      p += k*cnt;
    } else {
      long long start = min(a*p, t[q]);
      while (q < m && t[q] - start <= d) {
        q++;
      }
      p = (start + d) / a + 1;
      ans++;
    }
  }

  while (q < m) {
    long long start = t[q];
    while (q < m && t[q] - start <= d) {
      q++;
    }
    ans++;
  }

  cout << ans - 1 << endl;
}

E 問題

まず読解に苦しんだわけだけど、なんとかして問題文を理解したと思ったら WA で誤読で辛い問題だった。

F 問題

\(u o \to ou,\, o o \to u,\, k h \to h \) という書き換え規則が完備になるのは容易にわかるので、適当に正規形を求めて set に突っ込めば良い。

よく考えると \( u \to o o, k h \to h\) の方が自然。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

string reduce(string s) {
  for (int i = 0; i + 1 < s.size(); i++) {
    if (s.substr(i, 2) == "uo") {
      s.erase(i, 2);
      s.insert(i, "ou");
      return reduce(s);
    }
    if (s.substr(i, 2) == "oo") {
      s.erase(i, 2);
      s.insert(i, "u");
      return reduce(s);
    }
    if (s.substr(i, 2) == "kh") {
      s.erase(i, 2);
      s.insert(i, "h");
      return reduce(s);
    }
  }
  return s;
}

int main() {
  int n;
  cin >> n;

  set<string> st;
  while (n--) {
    string s;
    cin >> s;
    st.insert(reduce(s));
  }

  cout << st.size() << endl;
}

G 問題

コードが雑でごめん。

最小：まず有向辺だけを使って到達できる範囲を求める。実はこれが答えで、無向辺に対して（到達できない）→（到達できる）という向き付けをすれば良い。

最大：こちらも有向辺だけを使って到達できる範囲をうまく使う。まず到達可能範囲を求める。（到達できる）と（到達できない）を結ぶ辺に関しては、明らかに（到達できる）→（到達できない）の向き付けをすれば良い。問題サイズが小さくなって上手くいく。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

void solve_min(int n, int m, vector<int> us, vector<int> vs, vector<int> ds, vector<vector<int>> g, int s) {
  queue<int> q;
  q.push(s);

  vector<bool> vis(n);
  vis[s] = true;

  int cnt = 0;

  while (!q.empty()) {
    int u = q.front(); q.pop();
    cnt++;

    for (int i : g[u]) if (i % 2 == 0 && ds[i >> 1]) {
      int v = vs[i >> 1];

      if (!vis[v]) {
        q.push(v);
        vis[v] = true;
      }
    }
  }

  vector<int> ans(m);

  for (int i = 0; i < n; i++) {
    for (int ii : g[i]) if (!ds[ii >> 1]) {
      int v = ii % 2 == 0 ? vs[ii >> 1] : us[ii >> 1];
      if (!vis[i] && vis[v]) {
        ans[ii >> 1] = ii % 2 == 1;
      }
    }
  }

  cout << cnt << endl;
  for (int i = 0; i < m; i++) {
    if (!ds[i]) {
      putchar(ans[i] ? '-' : '+');
    }
  }
  cout << endl;
}

void solve_max(int n, int m, vector<int> us, vector<int> vs, vector<int> ds, vector<vector<int>> g, int s) {
  priority_queue<pair<int, int>> q;
  q.emplace(1, s);
  q.emplace(0, s);

  vector<bool> vis(n);
  vis[s] = true;

  int cnt = 0;

  vector<int> ans(m);

  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    cnt += d;

    if (d) {
      for (int i : g[u]) if (ds[i >> 1]) {
        int v = vs[i >> 1];
        if (!vis[v]) {
          q.emplace(0, v);
          q.emplace(1, v);
          vis[v] = true;
        }
      }
    } else {
      for (int i : g[u]) if (!ds[i >> 1]) {
        int v = i % 2 == 0 ? vs[i >> 1] : us[i >> 1];
        if (!vis[v]) {
          q.emplace(0, v);
          q.emplace(1, v);
          ans[i >> 1] = i % 2 == 1;
          vis[v] = true;
        }
      }
    }
  }

  cout << cnt << endl;
  for (int i = 0; i < m; i++) {
    if (!ds[i]) {
      putchar(ans[i] ? '-' : '+');
    }
  }
  cout << endl;
}

int main() {
  int n, m, s;
  cin >> n >> m >> s;
  s--;

  vector<int> us(m), vs(m), ds(m);
  vector<vector<int>> g(n);

  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &ds[i], &us[i], &vs[i]);
    ds[i] = ds[i] == 1;
    us[i]--;
    vs[i]--;

    if (ds[i]) {
      g[us[i]].push_back(i * 2);
    } else {
      g[us[i]].push_back(i * 2);
      g[vs[i]].push_back(i * 2 + 1);
    }
  }

  solve_max(n, m, us, vs, ds, g, s);
  solve_min(n, m, us, vs, ds, g, s);
}

H 問題

どの文字も偶数回ずつ現れているならば、答えは 1 である。そうでないとき、奇数回現れている文字があるなら、それらは全て奇数長回文の中心となるはずである。まず回文の個数を \(k\) 個と仮定して構成できるかを判定する。判定は単純な計算式で表せるため、容易なフェーズである。もし構成できないのであれば \(k \to k+2\) として再度チェックする。\(k+1\) が不可能なのはまあ分かると思う。これを繰り返すだけで良い。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int cnt[128];

int main() {
  int n;
  cin >> n;

  string s;
  cin >> s;

  for (char c : s) {
    cnt[c]++;
  }

  vector<char> center;
  int sum = 0;

  for (int i = 0; i < 128; i++) {
    if (cnt[i] % 2 == 1) {
      center.push_back(i);
      cnt[i]--;
    }
    sum += cnt[i] / 2;
  }

  if (center.empty()) {
    cout << 1 << endl;
    string ans(sum * 2, '\0');
    for (int i = 0; i < sum; i++) {
      for (int j = 0; j < 128; j++) {
        if (cnt[j] > 0) {
          ans[i] = ans[ans.size() - 1 - i] = j;
          cnt[j] -= 2;
          break;
        }
      }
    }
    cout << ans << endl;
    return 0;
  }

  while (true) {
    if (sum % center.size() == 0) {
      int g = sum / center.size();
      cout << center.size() << endl;
      for (char c : center) {
        string ans(g * 2 + 1, '*');
        ans[g] = c;
        for (int i = 0; i < g; i++) {
          for (int j = 0; j < 128; j++) {
            if (cnt[j] > 0) {
              ans[g - i - 1] = j;
              ans[g + i + 1] = j;
              cnt[j] -= 2;
              break;
            }
          }
        }
        cout << ans << ' ';
      }
      return 0;
    }
    for (int i = 0; i < 128; i++) {
      if (cnt[i] > 0) {
        cnt[i] -= 2;
        sum--;
        center.push_back(i);
        center.push_back(i);
        break;
      }
    }
  }
}

I 問題

二分探索する。[0,i) 番目まではいい感じの分割が得られている状態を dp[i] というブール値で表した時、遷移は dp[i]-> dp[i+K],dp[i+K+1],...,dp[j] な感じになって連続区間になる。ブール値でやる必要もないのでいもす法でやれば良い。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main() {
  int n, K;
  cin >> n >> K;

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  sort(a.begin(), a.end());

  int ok = 1e9, ng = -1;
  while (ok - ng > 1) {
    int mid = (ok + ng) / 2;

    vector<int> imos(n + 2);
    imos[0] = 1;
    imos[1] = -1;

    int j = 0;
    for (int i = 0; i < n; i++) {
      imos[i + 1] += imos[i];
      while (j < n && a[j] - a[i] <= mid) {
        j++;
      }
      if (imos[i] == 0) continue;
      if (j >= i + K) {
        imos[i + K]++;
        imos[j + 1]--;
      }
    }

    if (imos[n] > 0) {
      ok = mid;
    } else {
      ng = mid;
    }
  }

  cout << ok << endl;
}

K 問題

単純すぎて誤読してないか不安になる問題。i 番目が取りうる値の範囲を [L[i], R[i]] としたとき、L[i],R[i] から L[i+1],R[i+1] が計算できる。n 番目の値は R[n] にすれば良いのは明らかで、n,n-1,n-2,... の順に戻して行けば値が分かる。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

pair<int, int> intersect(int l, int r, int ll, int rr) {
  int a = max(l, ll);
  int b = min(r, rr);
  return make_pair(a, b);
}

int main() {
  int n;
  cin >> n;

  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a[i], &b[i]);
  }

  vector<int> L(n), R(n);
  L[0] = a[0];
  R[0] = a[0] + b[0];

  for (int i = 1; i < n; i++) {
    // L[i-1]-1 .. R[i-1]+1
    auto s = intersect(L[i - 1] - 1, R[i - 1] + 1, a[i], a[i] + b[i]);
    if (s.first > s.second) {
      cout << -1 << endl;
      return 0;
    }
    L[i] = s.first;
    R[i] = s.second;
  }

  vector<int> ans(n);
  ans[n - 1] = R[n - 1];
  int curr = R[n - 1];
  for (int i = n - 2; i >= 0; i--) {
    if (R[i] >= curr + 1) {
      curr++;
    } else if (R[i] >= curr) {
      // don't change
    } else {
      curr--;
    }
    ans[i] = curr;
  }

  long long des = 0;
  for (int i = 0; i < n; i++) {
    des += ans[i] - a[i];
  }
  cout << des << endl;

  for (int i = 0; i < n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
}

M 問題

これは良いよね。

まとめ

解いてない問題はそもそも読んですらない。E 問題に 1 時間費やしたのが、時間的にも体力的にも最悪だった。シンプルだけど面白い問題が多くて良かった。

Sandy the foodie

https://www.codechef.com/problems/KOK100

euler-tour tree。O(n log n) ではあるけど、定数倍が重くて通らなかった。

euler-tour を考えるとき辺で見るか、頂点で見るかどちらかだと思うけど、辺で考えると対称性が良い気がするので辺で実装している。今回の問題のように頂点に値を持たせる場合は、仮想的な何かを差し込んでおいてそれを使うと良い。

ACPC2017Day1 F Steps

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day1&pid=F

dyck 列（正しい括弧列）の数え上げ問題に、深さ上限を与えた問題。dyck 列の総数はカタラン数として知られる。解法の本質はカタラン数の二項係数表現の導出と同じで、エラーが起きた地点から移動方向を反転させるとよい。カタラン数については分かりやすいサイトが見つからなかったため参考リンクは用意していないが、『数学ガール』の 1 巻に書いてあった説明が分かりやすかった覚えがある（読んだの高 1 くらいなので、具体的に何が書かれてたか覚えてないけど）。定番ネタなので探せばいくらでもあるだろう。

たとえば左のような移動経路は、右の移動経路に対応させる。E (エラー地点）から移動方向を反転させている。

        *                 
 *     * G       *        
S-*---*---  <=> S-*-*------     
   E *             E *    
    *                 *   
                       * G'
                        * 

S→Gへの経路のうち、下側エラーが起きるパターン数は、S から G' への移動経路数と一致することが言える。ここまではカタラン数の計算方法として有名だろう。

今回は下側だけでなく上側も制約がつく。上側エラーも同様に計算できるが、下側と上側で二重カウントしてしまう。そのため包除原理的に重複を除去していく。

下側エラー→上側エラーとなるパターン数と上側エラー→下側エラーとなるパターン数もまた、先程と同様のテクニックにより計算できる（二回反転させる）。下側エラー→上側エラー→下側エラーというのも同様に計算できる（三階反転させる）。これらが計算できれば、包除原理的に解ける。下→上→下→上→…というのを永遠に求め続ける必要はなく、m の制約からして有限個である（m/n個程度であり、これは計算量に影響を与える）

計算量はわかりづらいが、O(n+m) になる。競技中には計算量解析が雑で、n≤500 のとき別の解法を取るような O( (n+m) sqrt(n) ) の解法を設計していたが、その必要はなかった。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

constexpr int mod = 1e9 + 7;

struct modint {
  int n;
  modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

modint fact[505050];
modint ifact[505050];
modint inv[505050];

modint C(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return fact[n] * ifact[r] * ifact[n - r];
}

modint g(int w, int y) {
  y = abs(y);
  if (w < y) return 0;
  if ((w - y) % 2 != 0) return 0;
  return C(w, (w - y) / 2);
}

int mirror(int y, int u) {
  return -(y - u) + u;
}

modint f(int w, int h, int y) {
  modint ret;
  ret += g(w, y);
  int y1 = y;
  int y2 = y;
  int d1 = -1;
  int d2 = h + 1;
  for (int ii = 0; min(-d1, d2) <= w; ii++) {
    y1 = mirror(y1, d1);
    y2 = mirror(y2, d2);
    if (ii & 1) {
      ret += g(w, y1);
      ret += g(w, y2);
    } else {
      ret -= g(w, y1);
      ret -= g(w, y2);
    }
    d1 -= h + 2;
    d2 += h + 2;
  }
  return ret;
}

int main() {
  fact[0] = 1;
  ifact[0] = 1;
  inv[1] = 1;
  for (int i = 2; i < 505050; i++) {
    inv[i] = inv[mod % i] * (mod - mod / i);
  }
  for (int i = 1; i < 505050; i++) {
    fact[i] = i * fact[i - 1];
    ifact[i] = inv[i] * ifact[i - 1];
  }
  int n, m;
  cin >> n >> m;

  modint ans = 0;
  for (int i = 0; i <= n - 1; i++) {
    ans += f(m, n - 1, i);
  }
  for (int i = 0; i <= n - 2; i++) {
    ans -= f(m, n - 2, i);
  }
  cout << ans.n << endl;
}

そういえば通り数って聞き馴染みがない（twitter 上でしか見ない）んだけど、よく使われる言葉なのだろうか？場合の数という表現は見覚えがある。

yukicoder No.569 3 x N グリッドのパスの数

https://yukicoder.me/problems/no/569

解法そのものは自明だが、真面目にやるべきものではない。行列による解法の存在に気づければ、解は線形漸化式に従うことが分かるので、その性質を使って楽をする。

解の列に対する母関数 a(x) を考える。ここである多項式 f(x) が存在して、f(x)a(x) の次数が L で抑えられる（つまり次数が高い場所では係数が 0 になる）。このような多項式を線形回帰列に対する annihilator と呼ぶらしい。annihilator を求めるアルゴリズムとして Berlekamp-Massey アルゴリズムが知られている [1]。具体値が既知で漸化式が未知のときに漸化式を求めるアルゴリズムとも考えられる。

annihilator を計算する際に、数列の具体値を計算する必要がある。これは graphillion などの ZDD 関連のライブラリを用いて計算できるが、自分が書いたコードは何故か遅かった（何かテクニックがあるのだろうか？）。以前に simpath を書いたことがあったので、そちらを使うことにする [2]。フロンティアが極めて小さいため、各フェーズにおける状態数は10～20個程度にしかならない。そのため、n=30 程度までなら一瞬で計算できる。試しに n=10^5 で計算させてみたところ 1.58 秒で結果が得られた。

[ 解答コード ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cassert>

using namespace std;

constexpr int mod = 1e9 + 7;

struct modint {
  int n;
  modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

modint modinv(modint n) {
  if (n.n == 1) return 1;
  return modinv(mod % n.n) * (mod - mod / n.n);
}
modint operator/(modint a, modint b) { return a * modinv(b); }

modint simpath(int n) {
  constexpr int H = 4;
  vector<pair<int, int>> es;
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < H; y++) {
      if (y + 1 < H) es.emplace_back(x * H + y, x * H + y + 1);
      if (x + 1 < n) es.emplace_back(x * H + y, x * H + y + H);
    }
  }
  vector<int> deg(n * H);
  for (auto e : es) {
    deg[e.first]++;
    deg[e.second]++;
  }
  map<map<int, int>, modint> dp0, dp1;
  dp0[{{0, 0}}] = 1;
  for (auto e : es) {
    const int u = e.first;
    const int v = e.second;
    deg[u]--;
    deg[v]--;
    dp1.clear();
    for (auto kv : dp0) {
      map<int, int> mate1 = kv.first;
      if (!kv.first.count(v)) mate1[v] = v;
      const int mu = mate1[u];
      const int mv = mate1[v];
      const bool del = deg[u] == 0 && u != 0;
      if (del) mate1.erase(u);
      if (deg[u] != 0 || (u != 0 && mu == u) || (u == 0 && mu != u) || mu == -1) dp1[mate1] += kv.second;
      if (mu == v || mu == -1 || mv == -1) continue;
      mate1[u] = -1;
      mate1[v] = -1;
      mate1[mu] = mv;
      mate1[mv] = mu;
      if (mate1[0] == -1) continue;
      if (del) mate1.erase(u);
      if (!del || mu != u) dp1[mate1] += kv.second;
    }
    swap(dp0, dp1);
  }
  return dp0.rbegin()->second;
}

// ref: https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm 
vector<modint> berlekamp_massey(vector<modint> s) {
  const int N = s.size();
  vector<modint> C(N);
  vector<modint> B(N);
  C[0] = 1;
  B[0] = 1;
  int L = 0;
  int m = 1;
  modint b = 1;
  for (int n = 0; n < N; n++) {
    modint d = s[n];
    for (int i = 1; i <= L; i++) d += C[i] * s[n - i];
    if (d.n == 0) {
      m++;
    } else if (2 * L <= n) {
      auto T = C;
      for (int i = 0; i + m < N; i++) C[i + m] -= B[i] * (d / b);
      L = n + 1 - L;
      B = T;
      b = d;
      m = 1;
    } else {
      for (int i = 0; i + m < N; i++) C[i + m] -= B[i] * (d / b);
      m++;
    }
  }
  C.resize(L + 1);
  reverse(C.begin(), C.end());
  assert(L < N - 1);
  return C;
}

vector<modint> poly_mod(vector<modint> a, const vector<modint> &m) {
  const int n = m.size();
  for (int i = a.size() - 1; i >= m.size(); i--) {
    for (int j = 0; j < m.size(); j++) {
      a[i - n + j] += a[i] * m[j];
    }
  }
  a.resize(m.size());
  return a;
}

// a*b mod m(x)
vector<modint> poly_mul(const vector<modint> &a, const vector<modint> &b, const vector<modint> &m) {
  vector<modint> ret(a.size() + b.size() - 1);
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < b.size(); j++) {
      ret[i + j] += a[i] * b[j];
    }
  }
  return poly_mod(ret, m);
}

// x^n mod m(x)
vector<modint> nth_power(long long n, const vector<modint> &m) {
  vector<modint> ret(1);
  vector<modint> x(2);
  ret[0] = x[1] = 1;
  while (n > 0) {
    if (n & 1) ret = poly_mul(ret, x, m);
    x = poly_mul(x, x, m);
    n /= 2;
  }
  return poly_mod(ret, m);
}

int main() {
  vector<modint> a(30);
  for (int i = 0; i < a.size(); i++) {
    a[i] = simpath(i + 1);
  }

  vector<modint> m = berlekamp_massey(a);
  m.pop_back();
  for (int i = 0; i < m.size(); i++) {
    m[i] *= mod - 1;
  }

  long long n;
  cin >> n;
  auto x = nth_power(n, m);

  modint ans;
  for (int i = 0; i < x.size(); i++) {
    ans += x[i] * a[i];
  }
  cout << ans.n << endl;
}

問題に関係のない simpath 関連のコードは以下の gist にまとめた。速さよりもコンパクトさを求めて書いた。まだ短くなる気がするので、劇的な改善策を見つけたい。コードもまだ綺麗とは言えない状態。『超高速グラフ列挙アルゴリズム』をまだ読んでないんだけど、もしかしたらコード、あるいは実装方法が載ってたりする？流石に載ってない？

https://gist.github.com/pekempey/80fb0978306cc077afa2800dd214cddd

[1] https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm
[2] http://pekempey.hatenablog.com/entry/2017/01/26/203424

ARC 082 E: ConvexScore

Keywords

convex hull DP

Time Complexity

\(O(N^3)\)

汎用的な処理が多数含まれているのでメモ。

#include <iostream>
#include <algorithm>
#include <vector>
#include <complex>
#include <cmath>
#include <cassert>
#include <tuple>

using namespace std;

constexpr long long mod = 998244353;

using P = complex<long long>;

long long dot(P a, P b) {
  return real(conj(a) * b);
}

long long cross(P a, P b) {
  return imag(conj(a) * b);
}

long long gcd(long long a, long long b) {
  a = abs(a);
  b = abs(b);
  if (b == 0) return a;
  return gcd(b, a % b);
}

// Get minimum element pointing in the same direction.
P tomato(P a) {
  long long g = gcd(a.real(), a.imag());
  return P(a.real() / g, a.imag() / g);
}

// Lexical order (argument, norm)
bool argcomp(P p1, P p2) {
  bool a = p1.imag() > 0 || (p1.imag() == 0 && p1.real() >= 0);
  bool b = p2.imag() > 0 || (p2.imag() == 0 && p2.real() >= 0);
  if (a != b) return a;
  long long c = p2.real() * p1.imag();
  long long d = p1.real() * p2.imag();
  if (c != d) return c < d;
  return norm(p1) < norm(p2);
}

namespace std {
  bool operator<(const P &a, const P &b) {
    return argcomp(a, b);
  }
}

int main() {
  int n;
  cin >> n;

  vector<P> ps(n);
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    ps[i] = P(x, y);
  }

  vector<pair<int, int>> es;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      es.emplace_back(i, j);
    }
  }
  // If two vectors are pointing same direction,
  // these are arranged such that both aren't taken.
  sort(es.begin(), es.end(), [&](pair<int, int> a, pair<int, int> b) {
    P d = ps[a.second] - ps[a.first];
    P e = ps[b.second] - ps[b.first];
    if (cross(d, e) == 0 && dot(d, e) >= 0) {
      return dot(ps[a.second] - ps[a.first], ps[b.first] - ps[a.first]) < 0;
    } else {
      return d < e;
    }
  });

  // Count the points inside (NOT on) the triangle(i,j,k)
  static int in[200][200][200];
  for (int j = 0; j < n; j++) {
    vector<pair<P, int>> qs;
    for (int i = 0; i < n; i++) {
      if (i == j) continue;
      qs.emplace_back(ps[i] - ps[j], i);
    }
    sort(qs.begin(), qs.end());
    for (int i = 0; i < n; i++) {
      if (i == j) continue;
      P s = tomato(ps[j] - ps[i]);
      int f = lower_bound(qs.begin(), qs.end(), make_pair(s, 0)) - qs.begin();
      for (int l = 0; l < n - 1; l++) {
        int k = qs[(f + l) % (n - 1)].second;
        in[i][j][k] -= l + 1;
        in[j][k][i] -= l + 1;
        in[k][i][j] -= l + 1;
      }
    }
  }
  static int on[200][200];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      for (int k = 0; k < n; k++) {
        if (i == k || j == k) continue;
        on[i][j] += cross(ps[k] - ps[i], ps[j] - ps[i]) == 0 && dot(ps[k] - ps[i], ps[j] - ps[i]) > 0 && dot(ps[k] - ps[j], ps[i] - ps[j]) > 0;
        in[i][j][k] = max(0, in[i][j][k] + n);
      }
    }
  }

  vector<long long> two(n + 1);
  two[0] = 1;
  for (int i = 1; i <= n; i++) {
    two[i] = two[i - 1] * 2 % mod;
  }

  // Easy
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    vector<long long> dp1(n);
    vector<long long> dp2(n);
    for (auto e : es) {
      int u = e.first;
      int v = e.second;

      if (u == i) {
        assert(dp1[v] == 0);
        dp1[v] = two[on[u][v]];
      } else if (v == i) {
        dp2[v] += dp2[u];
      } else {
        int c = on[i][v] + on[u][v] + in[i][u][v];
        dp2[v] += dp1[u] * two[c];
        dp2[v] += dp2[u] * two[c];
      }
      dp2[v] %= mod;
    }
    ans += dp2[i];
    ans %= mod;
  }

  cout << ans << endl;
}