Submission #2206075

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
using Line = tuple<int, int, int>;
const ll MOD = 998244353ll;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

ll mod_pow(ll x, ll e) {
  ll v = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) {
      v = v * x % MOD;
    }
    x = x * x % MOD;
  }
  return v;
}

Line getNormalizedLine(int x1, int y1, int x2, int y2) {
  int a = y2 - y1;
  int b = x1 - x2;
  int c = (-a * x1) + (-b * y1);
  int g = gcd(abs(a), abs(b));
  a /= g;
  b /= g;
  c /= g;
  if (a < 0) {
    a = -a;
    b = -b;
    c = -c;
  }
  if (a == 0 && b < 0) {
    b = -b;
    c = -c;
  }
  return Line(a, b, c);
}

int main() {
  int N;
  while (cin >> N) {
    vector<int> x(N), y(N);
    for (int i = 0; i < N; i++) {
      cin >> x[i] >> y[i];
    }
    map<Line, set<int>> linePoints;
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        Line line = getNormalizedLine(x[i], y[i], x[j], y[j]);
        linePoints[line].insert(i);
        linePoints[line].insert(j);
      }
    }
    ll ans = mod_pow(2, N);
    ans = (ans - 1 + MOD) % MOD;
    ans = (ans - N + MOD) % MOD;
    for (auto& entry : linePoints) {
      int k = entry.second.size();
      ll ng = (mod_pow(2, k) - k - 1 + MOD) % MOD;
      ans = (ans - ng + MOD) % MOD;
    }
    cout << ans << endl;
  }
  return 0;
}

Submission Info

Judge Result