Submission #237612

#	Time	Username	Problem	Language	Result	Execution time	Memory
237612		m3r8	The Forest of Fangorn (CEOI14_fangorn)	C++14	50 / 100	551 ms	65540 KiB

fangorn

#include <stdio.h>
#include <set>
#include <utility>
#include <functional>
#include <vector>

#define ii std::pair<long long ,long long>
#define N 3000
#define C 20100
#define ll long long


ll ccw(ll x1 , ll y1 , ll x2, ll y2){
  return x1 * y2 - x2 * y1;  
};

ii camps[C];
ii trees[N];

struct cmp{
  bool operator()(ii a, ii b){
    return ccw(a.first, a.second, b.first, b.second) >= 0; 
  };  
};

std::set<ii, cmp> sst[N];

int main(void){
  int w,h;
  scanf("%d %d",&w, &h);
  int xg, yg;
  scanf("%d %d",&xg, &yg);
  int c;
  scanf("%d",&c);

  for(int i = 0;i<c;i++){
    scanf("%d %d",&(camps[i].first), &(camps[i].second));  
  };
  int n;
  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<i;j++){
      sst[i].insert({trees[i].first - trees[j].first, trees[i].second-trees[j].second});
      sst[j].insert({trees[j].first - trees[i].first, trees[j].second-trees[i].second});
    };  
  };

  std::vector<int> erg;

  bool pos = 1;
  for(int i = 0;i<c;i++){
    for(int j = 0;j<n;j++){
      auto it = sst[j].upper_bound({camps[i].first - trees[j].first, camps[i].second - trees[j].second});  
      auto it2 = sst[j].upper_bound({xg - trees[j].first, yg - trees[j].second});
      bool ok = it == sst[j].end() && it2 == sst[j].begin() || it == sst[j].begin() && it2 == sst[j].end(); 
      if(it != it2 && !ok){
        pos = 0;  
      };
    };
    if(pos){
      erg.push_back(i+1);  
    };
    pos = 1;
  };
  
  printf("%d\n",erg.size());
  for(auto i: erg){
    printf("%d ",i);  
  };
  if(erg.size())puts("");

  return 0;  
};

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:37:56: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d %d",&(camps[i].first), &(camps[i].second));  
                   ~~~~~~~~~~~~~~~~~                    ^
fangorn.cpp:37:56: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:42:56: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d %d",&(trees[i].first), &(trees[i].second));  
                   ~~~~~~~~~~~~~~~~~                    ^
fangorn.cpp:42:56: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
fangorn.cpp:59:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       bool ok = it == sst[j].end() && it2 == sst[j].begin() || it == sst[j].begin() && it2 == sst[j].end(); 
                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:70:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",erg.size());
                 ~~~~~~~~~~^
fangorn.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&w, &h);
   ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&xg, &yg);
   ~~~~~^~~~~~~~~~~~~~~~~~
fangorn.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c);
   ~~~~~^~~~~~~~~
fangorn.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&(camps[i].first), &(camps[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
fangorn.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&(trees[i].first), &(trees[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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