oj.uz

답안 #259124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9018 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9017 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -