Submission #1560783

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MOD 998244353

LL powmod(LL a, LL n){
	if(n == 0) return 1;
	if(n % 2) return (a * powmod(a, n-1)) % MOD;
	LL c = powmod(a, n/2);
	return (c*c) % MOD;
}

struct UF{
	int n;
	vector<int> par;
	UF(int n) : n(n) {
		for(int i = 0; i < n; i++) par.push_back(i);
	}
	int find(int a){
		if(a != par[a]) par[a] = find(par[a]);
		return par[a];
	}
	void join(int a, int b){
		par[find(a)] = find(b);
	}
};


int main(){
	LL n = 0;
	cin >> n;
	pair<LL,LL> d[n];
	for(LL i = 0; i < n; i++){
		cin >> d[i].first >> d[i].second;
	}
	LL ans = powmod(2, n);
	//ans -= 1;
	//ans -= n;

	for(LL i = 0; i < n; i++){
		map<pair<LL,LL>, LL> f;
		for(LL j = i+1; j < n; j++){
			LL a1 = d[i].first - d[j].first;
			LL a2 = d[i].second - d[j].second;
			LL gc = __gcd(a1,a2);
			a1 /= gc; a2 /=gc;
			if(a1 < 0 || (a1 == 0 && a2 < 0)){
				a1 = -a1; a2 = -a2;
			}
			f[make_pair(a1,a2)] ++;
		}
		for(auto it = f.begin(); it != f.end(); it++){
			LL t = it->second;
			ans -= powmod(2,t);
			ans++;
		}
	}

	ans -= n;
	ans -= 1;
	ans %= MOD;
	while(ans < 0) ans += MOD;
	cout << ans << endl;
}

Submission Info

Judge Result