Submission #53717715

---

Source Code Expand

// LUOGU_RID: 159742336
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 998244353; 
const int N = 205; 

inline int poww(int a, int b) {
    int r = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P; 
    return r; 
}

int n; 
int x[N], y[N]; 
set<pair<i64, i64>> s; 

pair<i64, i64> calc(int i, int j) {
    if (x[i] == x[j]) return make_pair(1e18, (i64)(x[i] * 1e9 + 0.5)); 
    double k = 1.0 * (y[i] - y[j]) / (x[i] - x[j]); 
    double b = y[i] - k * x[i]; 
    return make_pair((i64)(k * 1e9 + 0.5), (i64)(b * 1e9 + 0.5)); 
}

int main(void) {
    ios::sync_with_stdio(0); 

    cin >> n; 
    int ans = poww(2, n) - n - 1; 
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i]; 
    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            auto it = calc(i, j); 

            if (s.count(it)) continue; 

            int cnt = 0; 

            for (int k = 1; k <= n; ++k) 
                if (i == k || j == k || calc(i, k) == it) ++cnt; 

            ans = (ans - poww(2, cnt) + cnt + 1) % P; 

            s.insert(it); 
        }
    cout << (ans + P) % P << "\n"; 
    return 0;
}

Submission Info

Judge Result