Submission #518268

#TimeUsernameProblemLanguageResultExecution timeMemory
518268kartelGeometrija (COCI21_geometrija)C++17
50 / 110
1090 ms336 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define pb push_back #define F first #define S second #define sz(x) (int)x.size() #define el "\n" #define pi (ld)acos(-1.0) //#pragma GCC target("avx2") //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef long double ld; const int N = 1e3 + 500; int n; int x[N], y[N]; int sg(ll x) { if (x < 0) { return 0; } return 1; } ll det(ll a, ll b, ll c, ll d) { return (a * d - b * c); } ld to_degrees(ld x) { return x * ld(180) / pi; } ld get_alpha(ld a, ld b, ld c) { // cerr << acos((a + b - c) / (2.0 * sqrt((ld)a) * sqrt((ld)b))) << el; return to_degrees(acos((a + b - c) / (2.0 * sqrt((ld)a) * sqrt((ld)b)))); } ll dist(ll a, ll b, ll c, ll d) { return ((a - c) * (a - c) + (b - d) * (b - d)); } vector <int> vc[2]; ld sf[N]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); // cerr.precision(10); // cerr << fixed; cin >> n; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } int ans = 0; for (int a = 0; a < n; a++) { for (int b = a + 1; b < n; b++) { vc[0].clear(); vc[1].clear(); for (int c = 0; c < n; c++) { if (a == c || b == c) { continue; } int sgn = sg(det(x[b] - x[a], y[b] - y[a], x[c] - x[a], y[c] - y[a])); // ll ab = dist(x[a], y[a], x[b], y[b]); // ll ac = dist(x[a], y[a], x[c], y[c]); // ll bc = dist(x[b], y[b], x[c], y[c]); vc[sgn].pb(c); } // // sort(all(vc[0]), // [&](pair <ld, ld> a, pair <ld, ld> b) { // return a.F > b.F; // }); // sort(all(vc[1]), // [&](pair <ld, ld> a, pair <ld, ld> b) { // return a.F < b.F; // }); // sf[sz(vc[0])] = 1e9; // for (int j = sz(vc[0]) - 1; j >= 0; j--) { // sf[j] = min(sf[j + 1], vc[0][j].S); // } // int i = 0; bool bad = 0; // for (auto p : vc[1]) { // ld alpha = p.F; // ld beta = p.S; // while (i < sz(vc[0]) && alpha + vc[0][i].F > 180) { // i++; // } // if (sf[i] + beta < 180.0) { // bad = 1; // break; // } // } for (int i = 0; i < sz(vc[0]) && !bad; i++) { int c = vc[0][i]; for (int j = 0; j < sz(vc[1]) && !bad; j++) { int d = vc[1][j]; int s1 = sg(det(x[b] - x[c], y[b] - y[c], x[d] - x[c], y[d] - y[c])); int s2 = sg(det(x[d] - x[b], y[d] - y[b], x[a] - x[b], y[a] - y[b])); int s3 = sg(det(x[a] - x[d], y[a] - y[d], x[c] - x[d], y[c] - y[d])); if (s1 == s2 && s1 == s3) { bad = 1; break; } } } if (!bad) { ans++; } } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...