oj.uz

Submission #64772

# Submission time Handle Problem Language Result Execution time Memory
64772 2018-08-05T15:11:44 Z bazsi700 The Forest of Fangorn (CEOI14_fangorn) C++14
40 / 100
 3000 ms 968 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define C complex<ll>
#define X real()
#define Y imag()

ll w,h,n,c;
C g;
C camp[2005];
C tree[10005];
bool can[15];

int sign(ll x) {
    if(x > 0) {
        return 1;
    } else if(x == 0) {
        return 0;
    } else {
        return -1;
    }
}

ll cross(C a, C b) { //-1 bal, 0 egyenes, 1 jobb A hoz képest a B
    return sign(((a*conj(b)).Y));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll gx,gy;
    cin >> w >> h >> gx >> gy >> c;
    g = {gx,gy};
    for(int i = 0; i < c; i++) {
        ll x,y;
        cin >> x >> y;
        camp[i] = {x,y};
    }
    cin >> n;
    for(int i = 0; i < n; i++) {
        ll x,y;
        cin >> x >> y;
        tree[i] = {x,y};
    }
    vector<int> pr;
    for(int i = 0; i < c; i++) {
        bool good = true;
        for(int a1 = 0; a1 < n && good; a1++) {
            for(int a2 = a1+1; a2 < n && good; a2++) {
                for(int b1 = 0; b1 < n && good; b1++) {
                    if(b1 == a1 || b1 == a2) {
                        continue;
                    }
                    for(int b2 = b1+1; b2 < n && good; b2++) {
                        if(b2 == a1 || b2 == a2) {
                            continue;
                        }
                        if(cross(tree[a2]-tree[a1],tree[b2]-tree[b1]) == 0) {
                            continue;
                        }
                        if(cross(tree[a2]-tree[a1],camp[i]-tree[a1]) == cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],camp[i]-tree[b1]) == cross(tree[b2]-tree[b1],g-tree[b1])) {
                            continue;
                        }
                        if(cross(tree[a2]-tree[a1],tree[b1]-tree[a1]) != cross(tree[a2]-tree[a1],tree[b2]-tree[a1])) {
                            continue;
                        }
                        if(cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) != cross(tree[b2]-tree[b1],tree[a2]-tree[b1])) {
                            continue;
                        }
                        if(cross(tree[a2]-tree[a1],tree[b1]-tree[a1]) != cross(tree[a2]-tree[a1],camp[i]-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) != cross(tree[b2]-tree[b1],camp[i]-tree[b1])) {
                            good = false;
                        }
                        if(cross(tree[a2]-tree[a1],tree[b1]-tree[a1]) != cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) != cross(tree[b2]-tree[b1],g-tree[b1])) {
                            good = false;
                        }
                    }
                }
            }
        }
        for(int a1 = 0; a1 < n && good; a1++) {
            for(int a2 = 0; a2 < n && good; a2++) {
                if(a1 == a2) {
                    continue;
                }
                int b1 = a2;
                for(int b2 = 0; b2 < n && good; b2++) {
                    if(b2 == a1 || b2 == a2) {
                        continue;
                    }
                    if(cross(tree[a2]-tree[a1],camp[i]-tree[a1]) == cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],camp[i]-tree[b1]) == cross(tree[b2]-tree[b1],g-tree[b1])) {
                        continue;
                    }
                    if(cross(tree[a2]-tree[a1],tree[b2]-tree[a1]) != cross(tree[a2]-tree[a1],camp[i]-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) != cross(tree[b2]-tree[b1],camp[i]-tree[b1])) {
                        good = false;
                    }
                    if(cross(tree[a2]-tree[a1],tree[b2]-tree[a1]) != cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) != cross(tree[b2]-tree[b1],g-tree[b1])) {
                        good = false;
                    }
                }
            }
        }
        if(good) {
            pr.push_back(i+1);
        }
    }
    cout << pr.size() << "\n";
    for(int el : pr) {
        cout << el << " ";
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 3 ms 712 KB Output is correct
8 Correct 160 ms 712 KB Output is correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 712 KB Output is correct
2 Correct 64 ms 728 KB Output is correct
3 Correct 405 ms 736 KB Output is correct
4 Correct 4 ms 736 KB Output is correct
5 Correct 8 ms 736 KB Output is correct
6 Correct 12 ms 736 KB Output is correct
7 Correct 2 ms 744 KB Output is correct
8 Correct 4 ms 792 KB Output is correct
9 Correct 228 ms 796 KB Output is correct
10 Execution timed out 3020 ms 800 KB Time limit exceeded
11 Execution timed out 3034 ms 804 KB Time limit exceeded
12 Execution timed out 3050 ms 808 KB Time limit exceeded

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 812 KB Output is correct
2 Correct 34 ms 816 KB Output is correct
3 Correct 27 ms 820 KB Output is correct
4 Execution timed out 3034 ms 824 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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