Submission #64774

#	Time	Username	Problem	Language	Result	Execution time	Memory
64774		bazsi700	The Forest of Fangorn (CEOI14_fangorn)	C++14	50 / 100	3045 ms	724 KiB

fangorn

#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;
        if(n <= 70) {
        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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20