oj.uz

답안 #518257

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518257 2022-01-23T09:13:28 Z kartel Geometrija (COCI21_geometrija) C++17
20 / 110
 913 ms 632 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 <pair <ld, ld> > 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({get_alpha(ab, bc, ac), get_alpha(ac, ab, bc)});
            }

            if (n <= 40) {
                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;
                    }
                }
                if (!bad) {
                    ans++;
                }
            }
        }
    }
    cout << ans;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 13 ms 332 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 6 ms 320 KB Output is correct
7 Correct 11 ms 324 KB Output is correct
8 Correct 12 ms 332 KB Output is correct
9 Correct 8 ms 320 KB Output is correct
10 Correct 10 ms 316 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 13 ms 332 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 6 ms 320 KB Output is correct
7 Correct 11 ms 324 KB Output is correct
8 Correct 12 ms 332 KB Output is correct
9 Correct 8 ms 320 KB Output is correct
10 Correct 10 ms 316 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 913 ms 340 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 13 ms 332 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 6 ms 320 KB Output is correct
7 Correct 11 ms 324 KB Output is correct
8 Correct 12 ms 332 KB Output is correct
9 Correct 8 ms 320 KB Output is correct
10 Correct 10 ms 316 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 913 ms 340 KB Output isn't correct
13 Halted 0 ms 0 KB -