Submission #2252122


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// EPS
constexpr double EPS = 1e-9;
/// --- Geometory Library {{{ ///
using Point = complex<int>;
#define X real()
#define Y imag()
#define dot(a, b) real(conj(a)*b)
#define cross(a, b) imag(conj(a)*b)
#define norm abs

// +1 : ccw
// -1 : cw
// +2 : a--b--c
// -2 : b--c--a
//  0 : b--a--c
// int ccw(Point a, Point b, Point c) {
//   b -= a; c -= a;
//   if(cross(b, c) > EPS) return +1;
//   if(cross(b, c) < -EPS) return -1;
//   if(dot(b, c) < 0) return 0;
//   if(norm(b) < norm(c)) return +2;
//   return -2;
// }
//
// double arg(Point a, Point b) {
//   return acos(dot(a, b) / norm(a) / norm(b));
// }
/// ---}}} ///

bool para(Point a, Point b, Point c) {
  b -= a; c -= a;
  return b.X * c.Y == b.Y * c.X;
}

constexpr ll mod = 998244353;

/// --- modulo Library {{{ ///
constexpr ll extgcd(ll a, ll b, ll& x, ll& y) {
  if(b==0) {
    x = 1; y = 0;
    return a;
  }
  ll d = extgcd(b, a % b, y, x);
  y -= (a / b) * x;
  return d;
}
constexpr ll modpow(ll a, ll b, ll mod = 1e9 + 7) {
  a = (a % mod + mod) % mod;
  ll r = 1;
  while(b){
    if(b & 1) r = r * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return r;
}
constexpr ll modinv(ll a, ll mod = 1e9 + 7) {
  a = (a % mod + mod) % mod;
  ll x = 0, y = 0;
  extgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}
template<int N, int mod = 1e9 + 7> struct Factorial {
  int arr[N+1], inv[N+1];
  int operator[](int i) const { return arr[i]; }
  constexpr Factorial(): arr(), inv() {
    arr[0] = 1;
    for(int i = 1; i <= N; i++) {
      arr[i] = (ll) i * arr[i - 1] % mod;
    }
    inv[N] = modinv(arr[N], mod);
    for(int i = N-1; i >= 0; i--) {
      inv[i] = (ll) (i + 1) * inv[i + 1] % mod;
    }
  }
  int C(int n, int r) const {
    if(n < 0 || r < 0 || n < r) return 0;
    return (ll) arr[n] * inv[r] % mod * inv[n - r] % mod;
  }
};
/// }}}--- ///

constexpr Factorial<200, mod> fact;

bool done[200][200];

// 点集合のうち,(同一直線上の点のみを選ぶ)を覗いた集合の数とスコアが一致
// O(N^3)
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n; cin >> n;
  vector<Point> p(n);
  for(int i = 0; i < n; i++) {
    int x, y; cin >> x >> y;
    p[i] = Point(x, y);
  }
  ll ans = modpow(2, n, mod) - fact.C(n, 2) - n - 1;
  ans %= mod;
  for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) {
    if(done[i][j]) continue;
    int cnt = 2;
    vector<int> vs;
    vs.emplace_back(i);
    vs.emplace_back(j);
    for(int k = j + 1; k < n; k++) {
      if(para(p[i], p[j], p[k])) cnt++, vs.emplace_back(k);
    }
    for(int s = 0; s < (int) vs.size(); s++) for(int t = s + 1; t < (int) vs.size(); t++) {
      done[vs[s]][vs[t]] = 1;
    }
    ans -= modpow(2, cnt, mod) - fact.C(cnt, 2) - cnt - 1;
    ans %= mod;
  }
  cout << (ans + mod) % mod << endl;
}

Submission Info

Submission Time
Task E - ConvexScore
User luma
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2976 Byte
Status AC
Exec Time 7 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 36
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 256 KB
1_005.txt AC 3 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 3 ms 256 KB
1_008.txt AC 2 ms 256 KB
1_009.txt AC 3 ms 256 KB
1_010.txt AC 2 ms 256 KB
1_011.txt AC 3 ms 256 KB
1_012.txt AC 4 ms 256 KB
1_013.txt AC 3 ms 256 KB
1_014.txt AC 1 ms 256 KB
1_015.txt AC 1 ms 256 KB
1_016.txt AC 1 ms 256 KB
1_017.txt AC 6 ms 256 KB
1_018.txt AC 7 ms 256 KB
1_019.txt AC 4 ms 256 KB
1_020.txt AC 4 ms 256 KB
1_021.txt AC 5 ms 256 KB
1_022.txt AC 5 ms 256 KB
1_023.txt AC 6 ms 256 KB
1_024.txt AC 6 ms 256 KB
1_025.txt AC 6 ms 256 KB
1_026.txt AC 5 ms 256 KB
1_027.txt AC 1 ms 256 KB
1_028.txt AC 1 ms 256 KB
1_029.txt AC 5 ms 256 KB
1_030.txt AC 6 ms 256 KB
1_031.txt AC 6 ms 256 KB
1_032.txt AC 6 ms 256 KB
1_033.txt AC 6 ms 256 KB
1_034.txt AC 6 ms 256 KB
1_035.txt AC 4 ms 256 KB