oj.uz

Submission #874016

# Submission time Handle Problem Language Result Execution time Memory
874016 2023-11-16T07:47:42 Z TAhmed33 Kućice (COCI21_kucice) C++
40 / 110
 1000 ms 860 KB 
#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].first <= arr[i].first) 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;
			int o2 = 0;
			for (auto p : x) {
				if (p == x[l]) continue;
				if (ok(p, x[l], arr[i])) o2++;
			}
			cnt = add(cnt, pw[o2]);
		}
		ans = add(ans, sub(pw[n], cnt));
	}
	cout << sub(ans, n) << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:65:8: warning: variable 'o' set but not used [-Wunused-but-set-variable]
   65 |    int o = 0;
      |        ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 957 ms 660 KB Output is correct
7 Execution timed out 1004 ms 604 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Execution timed out 1010 ms 652 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 0 ms 596 KB Output is correct
15 Correct 0 ms 604 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 0 ms 596 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 0 ms 600 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 3 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 3 ms 860 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 2 ms 604 KB Output is correct
28 Correct 2 ms 604 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 2 ms 604 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 957 ms 660 KB Output is correct
7 Execution timed out 1004 ms 604 KB Time limit exceeded
8 Halted 0 ms 0 KB -