제출 #1152593

#제출 시각아이디문제언어결과실행 시간메모리
1152593gelastropodGeometrija (COCI21_geometrija)C++20
50 / 110
1094 ms444 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...