Submission #876855

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876855	2023-11-22T12:39:18 Z	Mizo_Compiler	Kućice (COCI21_kucice)	C++17	40 / 110	1000 ms	604 KB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
typedef complex<ll> point;
#define X real()
#define Y imag()
const int N = 1005, M = 1e9+7;
int n;
point pp[N];
ll dir(point a, point b, point c) {
	return (conj(c-a) * (c-b)).Y;
}

pair<int, int> pts[N];
ll pw[N];

ll mul(ll a, ll b) {
	return (a * b) % M;
}

ll add(ll a, ll b) {
	a += b;
	return (a >= M ? a-M : a);
}

ll sub(ll a, ll b) {
	a -= b;
	return (a < 0 ? a+M : a);
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> pts[i].F >> pts[i].S;
		pp[i] = {pts[i].F, pts[i].S};
	}
	if (n == 1) {
		cout << 1;
		return 0;
	}
	if (n == 2) {
		cout << 4;
		return 0;
	}
	if (n == 3) {
		cout << 12;
		return 0;
	}
	sort(pts, pts+n);
	pw[0] = 1;
	ll ans = 0;
	for (int i = 1; i < N; i++) {
		pw[i] = (pw[i-1] * 2) % M;
	}
	for (int i = 0; i < n; i++) {
		ll cnt = 0;
		for (int j = 0; j < n; j++) {
			if (j == i)continue;
			int c = 0;
			for (int k = 0; k < n; k++) {
				if (k == i || k == j)continue;
				c += (dir(pp[j], pp[i], pp[k]) < 0);
			}
			cnt = add(cnt, pw[c]);
		}
		ans = add(ans, sub(pw[n], cnt));
	}
	cout << sub(ans, n) << "\n";
}

Subtask #1

0 / 10.0

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

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Execution timed out	1089 ms	484 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	0 ms	460 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	460 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	468 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	600 KB	Output is correct
15	Correct	0 ms	348 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	0 ms	460 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	460 KB	Output is correct
5	Correct	0 ms	600 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	468 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	600 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	464 KB	Output is correct
22	Correct	2 ms	348 KB	Output is correct
23	Correct	2 ms	348 KB	Output is correct
24	Correct	2 ms	344 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	3 ms	344 KB	Output is correct
27	Correct	2 ms	348 KB	Output is correct
28	Correct	2 ms	348 KB	Output is correct
29	Correct	2 ms	348 KB	Output is correct
30	Correct	2 ms	348 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	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Execution timed out	1092 ms	604 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-