oj.uz

Submission #518268

# Submission time Handle Problem Language Result Execution time Memory
518268 2022-01-23T09:37:28 Z kartel Geometrija (COCI21_geometrija) C++17
50 / 110
 1000 ms 336 KB 
#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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 44 ms 320 KB Output is correct
13 Correct 44 ms 332 KB Output is correct
14 Correct 33 ms 284 KB Output is correct
15 Correct 31 ms 308 KB Output is correct
16 Correct 51 ms 332 KB Output is correct
17 Correct 43 ms 332 KB Output is correct
18 Correct 43 ms 204 KB Output is correct
19 Correct 45 ms 204 KB Output is correct
20 Correct 55 ms 332 KB Output is correct
21 Correct 51 ms 320 KB Output is correct
22 Correct 43 ms 332 KB Output is correct
23 Correct 44 ms 312 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 44 ms 320 KB Output is correct
13 Correct 44 ms 332 KB Output is correct
14 Correct 33 ms 284 KB Output is correct
15 Correct 31 ms 308 KB Output is correct
16 Correct 51 ms 332 KB Output is correct
17 Correct 43 ms 332 KB Output is correct
18 Correct 43 ms 204 KB Output is correct
19 Correct 45 ms 204 KB Output is correct
20 Correct 55 ms 332 KB Output is correct
21 Correct 51 ms 320 KB Output is correct
22 Correct 43 ms 332 KB Output is correct
23 Correct 44 ms 312 KB Output is correct
24 Execution timed out 1090 ms 336 KB Time limit exceeded
25 Halted 0 ms 0 KB -