Submission #1152516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152516		gelastropod	Geometrija (COCI21_geometrija)	C++20	0 / 110	1 ms	320 KiB

geometrija

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	int n, a, b;
	cin >> n;
	vector<pair<int, int>> points;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		points.push_back({ a, b });
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (points[i] == points[j]) continue;
			int _small = min(points[i].second, points[j].second);
			int _big = max(points[i].second, points[j].second);
			int small = min(points[i].first, points[j].first);
			int big = max(points[i].first, points[j].first);
			bool works = true;
			for (int k = 0; k < n; k++) {
				if (points[i] == points[k] || points[j] == points[k]) continue;
				for (int l = k + 1; l < n; l++) {
					if (points[i] == points[l] || points[j] == points[l] || points[k] == points[l]) continue;
					int _osmall = min(points[k].second, points[l].second);
					int _obig = max(points[k].second, points[l].second);
					int osmall = min(points[k].first, points[l].first);
					int obig = max(points[k].first, points[l].first);
					if (i == k || j == k || i == l || j == l) continue;
					if (points[i].first != points[j].first && points[k].first != points[l].first) {
						long double m1 = ((long double)points[j].second - points[i].second) / (points[j].first - points[i].first);
						long double m2 = ((long double)points[l].second - points[k].second) / (points[l].first - points[k].first);
						long double c1 = (long double)points[i].second - m1 * points[i].first;
						long double c2 = (long double)points[k].second - m2 * points[k].first;
						if (abs(m1 - m2) < 1e-10 && abs(c1 - c2) > 1e-10) continue;
						if (abs(m1 - m2) < 1e-10 && (big > osmall || small < obig)) {
							works = false;
							break;
						}
						long double x = (c2 - c1) / (m1 - m2);
						if (small < x && x < big && osmall < x && x < obig) {
							works = false;
							break;
						}
					}
					if (points[i].first != points[j].first) {
						long double m1 = ((long double)points[j].second - points[i].second) / (points[j].first - points[i].first);
						long double c1 = (long double)points[i].second - m1 * points[i].first;
						long double y = m1 * points[k].first + c1;
						if (_osmall < y && y < _obig && small < osmall && big > osmall) {
							works = false;
							break;
						}
					}
					if (points[k].first != points[l].first) {
						long double m2 = ((long double)points[l].second - points[k].second) / (points[l].first - points[k].first);
						long double c2 = (long double)points[k].second - m2 * points[k].first;
						long double y = m2 * points[i].first + c2;
						if (osmall < small && obig > small && _small < y && y < _big) {
							works = false;
							break;
						}
					}
					if (points[i].first == points[k].first && (_small < _obig || _big > _osmall)) {
						works = false;
						break;
					}
				}
				if (!works) break;
			}
			ans += works;
		}
	}
	cout << ans << '\n';
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60