Submission #874398

#	Time	Username	Problem	Language	Result	Execution time	Memory
874398		TAhmed33	Kućice (COCI21_kucice)	C++98	0 / 110	1 ms	604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int add (int a, int b) {
	a += b; if (a >= MOD) a -= MOD;
	return a;
}
int sub (int a, int b) {
	a -= b; if (a < 0) a += MOD;
	return a;
}
int mul (int a, int b) {
	return (1ll * a * b) % MOD;
}
int pw[20001];
int n;
pair <int, int> arr[1001];
int cross (pair <int, int> x, pair <int, int> y) {
	return x.first * y.second - x.second * y.first;
}
pair <int, int> sub2 (pair <int, int> a, pair <int, int> b) {
	return {a.first - b.first, a.second - b.second};
}
bool ok (pair <int, int> p, pair <int, int> s1, pair <int, int> s2) {
	return cross(sub2(p, s1), sub2(p, s2)) < 0;
}
signed main () {
	pw[0] = 1; for (int i = 1; i <= 20000; i++) pw[i] = mul(2, pw[i - 1]);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	if (n == 1) {
		cout << "1\n"; return 0;
	}
	if (n == 2) {
		cout << "4\n"; return 0;
	}
	if (n == 3) {
		cout << "12\n"; return 0;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		vector <pair <int, int>> x, y;
		for (int j = 1; j <= n; j++) {
			if (j != i) {
				if (arr[j].second <= arr[i].second) x.push_back(arr[j]);
				else y.push_back(arr[j]);
			}
		}
		sort(x.begin(), x.end(), [&] (pair <int, int> &a, pair <int, int> &b) {
			return cross(sub2(a, arr[i]), sub2(b, a)) > 0;
		});
		sort(y.begin(), y.end(), [&] (pair <int, int> &a, pair <int, int> &b) {
			return cross(sub2(a, arr[i]), sub2(b, a)) > 0;
		});
		for (auto j : y) x.push_back(j);
		int cnt = 0;
		int r = 1;
		for (int l = 0; l < n - 1; l++) {
			r = (r + 1) % (n - 1);
			while (r != l && ok(x[r], x[l], arr[i])) r = (r + 1) % (n - 1);
			r = (r - 1 + n - 1) % (n - 1);
			int o = 0;
			if (r >= l) o = r - l;
			else o = r + (n - 1) - l;
			cnt = add(cnt, pw[o]);
		}
		ans = add(ans, sub(pw[n], cnt));
	}
	cout << sub(ans, n) << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 30
• Subtask 5: 0 / 30