제출 #876855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876855		Mizo_Compiler	Kućice (COCI21_kucice)	C++17	40 / 110	1092 ms	604 KiB

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
• Subtask 2: 0 / 30
• Subtask 3: 10 / 10
• Subtask 4: 30 / 30
• Subtask 5: 0 / 30