oj.uz

Submission #64783

# Submission time Handle Problem Language Result Execution time Memory
64783 2018-08-05T16:09:09 Z bazsi700 The Forest of Fangorn (CEOI14_fangorn) C++14
20 / 100
 3000 ms 4624 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));
}

bool isbad[2005][2005];
bool isbadv[2005];
int leftest[2005];
int rightest[2005];

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};
    }
    for(int i = 0; i < n; i++) {
        bool bad = false;
        int fix = (i == 0 ? 1 : 0);
        for(int j = 0; j < n; j++) {
            if(j == i || j == fix) {
                continue;
            }
            if(cross(tree[fix]-tree[i],tree[j]-tree[i]) > 0) {
                fix = j;
            }
        }
        for(int j = 0; j < n; j++) {
            if(j == i || j == fix) {
                continue;
            }
            if(cross(tree[fix]-tree[i],tree[j]-tree[i]) > 0) {
                bad = true;
            }
        }
        if(bad) {
            isbadv[i] = true;
            for(int j = 0; j < n; j++) {
                isbad[i][j] = isbad[j][i] = true;
            }
        } else {
            leftest[i] = fix;
        }
    }
    for(int i = 0; i < n; i++) {
        if(isbadv[i]) {
            continue;
        }
        int fix = (i == 0 ? 1 : 0);
        for(int j = 0; j < n; j++) {
            if(j == i || j == fix) {
                continue;
            }
            if(cross(tree[fix]-tree[i],tree[j]-tree[i]) < 0) {
                fix = j;
            }
        }
        rightest[i] = fix;
       // cout << i << " " << leftest[i] << " " << rightest[i] << "a\n";
    }
    vector<int> pr;
    for(int i = 0; i < c; i++) {
        bool good = true;
        for(int x = 0; x < n; x++) {
            for(int y = x+1; y < n; y++) {
                if(isbad[x][y]) {
                    if(cross(tree[y]-tree[x],g-tree[x]) == -cross(tree[y]-tree[x],camp[i]-tree[x])) {
                        good = false;
                    }
                }
            }
        }
       // cout << good << "\n";
        if(!good) {
            continue;
        }
        for(int a2 = 0; a2 < n; a2++) {
            if(!isbadv[a2]) {
                int b1 = a2;
                int a1 = leftest[a2];
                int b2 = rightest[a2];
                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;
                 //   cout << a1 << " " << b1 << " " << b2 << endl;
                }
                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;
               //     cout << a1 << " " << b1 << " " << b2 << endl;
                }
            }
        }
        if(good) {
            pr.push_back(i+1);
        }
    }
    cout << pr.size() << "\n";
    for(int el : pr) {
        cout << el << " ";
    }
    return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Correct 2 ms 428 KB Output is correct
3 Incorrect 2 ms 428 KB Output isn't correct
4 Correct 3 ms 428 KB Output is correct
5 Incorrect 2 ms 464 KB Output isn't correct
6 Incorrect 1 ms 572 KB Output isn't correct
7 Correct 3 ms 576 KB Output is correct
8 Incorrect 3 ms 600 KB Output isn't correct

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Incorrect 3 ms 724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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