Submission #1152593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152593		gelastropod	Geometrija (COCI21_geometrija)	C++20	50 / 110	1094 ms	444 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++) {
			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++) {
				for (int l = k + 1; l < n; l++) {
					int _small = min(points[i].second, points[j].second);
					int _big = max(points[i].second, points[j].second);
					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 (m1 == m2 && c1 != c2) continue;
						if (m1 == m2 && (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;
						}
					}
					else 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 x = m1 * points[k].first + c1;
						if (_osmall < x && x < _obig && small < osmall && big > osmall) {
							works = false;
							break;
						}
					}
					else 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 x = m2 * points[i].first + c2;
						if (osmall < small && obig > small && _small < x && x < _big) {
							works = false;
							break;
						}
					}
				}
				if (!works) break;
			}
			ans += works;
		}
	}
	cout << ans << '\n';
}

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