oj.uz

Submission #259124

# Submission time Handle Problem Language Result Execution time Memory
259124 2020-08-07T08:30:26 Z 강태규(#5095) 별자리 2 (JOI14_constellation2) C++14
15 / 100
 9000 ms 504 KB 
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int n;
int X[3001], Y[3001], C[3001];

int ccw(pii a, pii b) {
    llong val = 1ll * a.x * b.y - 1ll * a.y * b.x;
    if (val < 0) return -1;
    if (val > 0) return 1;
    return 0;
}

int ccw(int a, int b, int c) {
    return ccw(pii(X[b] - X[a], Y[b] - Y[a]), pii(X[c] - X[b], Y[c] - Y[b]));
}

bool in(int a, int b, int c, int d) {
    int cnt[3] = {};
    ++cnt[ccw(a, b, d) + 1];
    ++cnt[ccw(b, c, d) + 1];
    ++cnt[ccw(c, a, d) + 1];
    return !cnt[0] || !cnt[2];
}
bool inter(int a, int b, int c, int d) {
    return ccw(a, b, c) != ccw(a, b, d) && ccw(c, d, a) != ccw(c, d, b);
}

#define FOR(a) for (int a = 1; a <= n; ++a) { if (used[a]) continue; used[a] = 1; {
#define END(a) } used[a] = 0; }

int used[3001];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> X[i] >> Y[i] >> C[i];
    int ans = 0;
    FOR(a) FOR(b) FOR(c) FOR(d) FOR(e) FOR(f) {
        bool pos = 1;
        if (pos) if (C[a] != 0 || C[b] != 1 || C[c] != 2) pos = 0;
        if (pos) if (C[d] != 0 || C[e] != 1 || C[f] != 2) pos = 0;
        if (pos) if (in(a, b, c, d) || in(a, b, c, e) || in(a, b, c, f)) pos = 0;
        if (pos) if (in(d, e, f, a) || in(d, e, f, b) || in(d, e, f, c)) pos = 0;
        if (pos) if (inter(a, b, d, e)) pos = 0;
        if (pos) if (inter(b, c, d, e)) pos = 0;
        if (pos) if (inter(c, a, d, e)) pos = 0;
        if (pos) if (inter(a, b, e, f)) pos = 0;
        if (pos) if (inter(b, c, e, f)) pos = 0;
        if (pos) if (inter(c, a, e, f)) pos = 0;
        if (pos) if (inter(a, b, f, d)) pos = 0;
        if (pos) if (inter(b, c, f, d)) pos = 0;
        if (pos) if (inter(c, a, f, d)) pos = 0;
        if (pos) ++ans;
    }
    END(f) END(e) END(d) END(c) END(b) END(a)
    printf("%d\n", ans / 2);
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 132 ms 384 KB Output is correct
6 Correct 481 ms 504 KB Output is correct
7 Correct 1381 ms 504 KB Output is correct
8 Correct 1316 ms 504 KB Output is correct
9 Correct 1377 ms 504 KB Output is correct
10 Correct 486 ms 504 KB Output is correct
11 Correct 1340 ms 396 KB Output is correct
12 Correct 1362 ms 400 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9018 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9017 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -