Submission #1143733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143733		dpsaveslives	The Forest of Fangorn (CEOI14_fangorn)	C++20	100 / 100	2216 ms	32012 KiB

fangorn

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
int N,C,W,H;
pii G;
pii camps[10010], trees[2010], lines[2010][2010];
pii sub(pii a, pii b){
    return {a.f-b.f,a.s-b.s};
}
bool cmp(pii a, pii b){
    int c = a.f+(!a.f)*a.s, d = b.f+(!b.f)*b.s;
    if(!c) return false;
    if(!d) return true;
    if(c < 0 && d > 0) return false;
    if(c > 0 && d < 0) return true;
    return (ll)a.s*b.f > (ll)a.f*b.s;
}
int finden(int i, pii a){
    return (upper_bound(lines[i],lines[i]+N-1,a,cmp)-lines[i])%(N-1);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> W >> H >> G.f >> G.s >> C;
    for(int i = 0;i<C;++i){
        cin >> camps[i].f >> camps[i].s;
    }
    cin >> N;
    for(int i = 0;i<N;++i){
        cin >> trees[i].f >> trees[i].s;
    }
    for(int i = 0;i<N;++i){
        for(int j = 0;j<N;++j){
            lines[i][j] = sub(trees[i],trees[j]);
        }
        sort(lines[i],lines[i]+N,cmp);
    }
    vector<int> ans;
    for(int i = 0;i<C;++i){
        bool poss = true;
        for(int j = 0;j<N;++j){
            if(finden(j,sub(G,trees[j])) != finden(j,sub(camps[i],trees[j]))){
                poss = false;
                break;
            }
        }
        if(poss) ans.push_back(i+1);
    }
    cout << ans.size() << "\n";
    for(int i = 0;i<ans.size();++i){
        if(i == ans.size()-1) cout << ans[i] << "\n";
        else cout << ans[i] << " ";
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20