Submission #667821

#	Time	Username	Problem	Language	Result	Execution time	Memory
667821		RambaXGorilla	The Forest of Fangorn (CEOI14_fangorn)	C++17	100 / 100	2272 ms	32092 KiB

fangorn

#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair <int,int> ii;
int N, C, W, H;
ii gimli;
ii camps[10010];
ii trees[2010];
ii rays[2010][2010];
vector <int> reach;
ii sub(ii a, ii b) {return ii(a.first - b.first, a.second - b.second);}
bool comp(ii a, ii b){
    int c = a.first + (!a.first) * a.second;
    int d = b.first + (!b.first) * b.second;
    if(!c) return false;
    if(!d) return true;
    if(c < 0 && d > 0) return false;
    if(d < 0 && c > 0) return true;
    return (ll) a.second * b.first > (ll) b.second * a.first;
}
int search(int j, ii a){
    return (upper_bound(rays[j], rays[j] + N - 1, a, comp) - rays[j]) % (N - 1);
}
int main(){
    scanf("%d%d%d%d",&W,&H,&gimli.first,&gimli.second);
    scanf("%d",&C);
    for(int i = 0;i < C;i++){
        scanf("%d%d",&camps[i].first,&camps[i].second);
    }
    scanf("%d",&N);
    for(int i = 0;i < N;i++){
        scanf("%d%d",&trees[i].first,&trees[i].second);
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            rays[i][j] = sub(trees[i], trees[j]);
        }
        sort(rays[i], rays[i] + N, comp);
    }
    for(int i = 0;i < C;i++){
        bool poss = true;
        for(int j = 0;j < N;j++){
            if(search(j, sub(gimli, trees[j])) != search(j, sub(camps[i], trees[j]))){
                poss = false;
                break;
            }
        }
        if(poss) reach.push_back(i + 1);
    }
    printf("%d\n",reach.size());
    for(auto i : reach){
        printf("%d ",i);
    }
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:53:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   53 |     printf("%d\n",reach.size());
      |             ~^    ~~~~~~~~~~~~
      |              |              |
      |              int            std::vector<int>::size_type {aka long unsigned int}
      |             %ld
fangorn.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d%d%d%d",&W,&H,&gimli.first,&gimli.second);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d",&C);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d",&camps[i].first,&camps[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
fangorn.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d%d",&trees[i].first,&trees[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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