Submission #29686

#TimeUsernameProblemLanguageResultExecution timeMemory
29686rondojimThe Forest of Fangorn (CEOI14_fangorn)C++14
10 / 100
649 ms2120 KiB
#include <stdio.h> #include <algorithm> #include <vector> using namespace std; struct pt{ pt(){x = y = p = 0;}; pt(int x_, int y_){ x = x_; y = y_; p = -1; if (y == 0 && x > 0) p = 0; if (y > 0) p = 1; if (y == 0 && x < 0) p = 2; if (y < 0) p = 3; } int x,y,p; bool operator <(const pt& t) const{ if (p != t.p) return p < t.p; return (long long) y * t.x < (long long) t.y * x; }; }P[4040]; int main() { scanf ("%*d %*d"); int x,y; scanf ("%d %d",&x,&y); int M, CX[10020], CY[10020]; scanf ("%d",&M); for (int i=0;i<M;i++) scanf ("%d %d",&CX[i],&CY[i]); int N, TX[2020], TY[2020]; scanf ("%d",&N); for (int i=0;i<N;i++) scanf ("%d %d",&TX[i],&TY[i]); vector<int> res; for (int i=0;i<M;i++) res.push_back(i); for (int i=0;i<N;i++){ int c = 0; for (int j=0;j<N;j++) if (i != j){ pt u(-(TX[j]-TX[i]),-(TY[j]-TY[i])); P[c++] = u; if (u.p == 0 || u.p == 1){ u.p += 4; P[c++] = u; } } pt v(x-TX[i],y-TY[i]); P[c++] = v; sort(P,P+c); for (int j=0;j<c;j++) if (P[j].x == v.x && P[j].y == v.y){ vector<int> nxt; for (auto &k : res){ pt u(CX[k] - TX[i], CY[k] - TY[i]); if (P[j-1] < u && u < P[j+1]){nxt.push_back(k); continue;} u.p += 4; if (P[j-1] < u && u < P[j+1]) nxt.push_back(k); } res = nxt; break; } } printf ("%d\n",res.size()); for (auto &x : res) printf ("%d ",++x); return 0; }

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:63: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",res.size());
                           ^
fangorn.cpp:24:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%*d %*d");
                   ^
fangorn.cpp:26:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int x,y; scanf ("%d %d",&x,&y);
                                ^
fangorn.cpp:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&M);
                 ^
fangorn.cpp:29:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<M;i++) scanf ("%d %d",&CX[i],&CY[i]);
                                                     ^
fangorn.cpp:31:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&N);
                 ^
fangorn.cpp:32:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<N;i++) scanf ("%d %d",&TX[i],&TY[i]);
                                                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...