Submission #101032

#TimeUsernameProblemLanguageResultExecution timeMemory
101032BruteforcemanThe Forest of Fangorn (CEOI14_fangorn)C++11
80 / 100
3034 ms1768 KiB
#include "bits/stdc++.h" using namespace std; struct point { long long x, y; int id; point () {} point (long long x, long long y) : x(x), y(y) {} point operator + (point p) { return point(x + p.x, y + p.y); } point operator - (point p) { return point(x - p.x, y - p.y); } } c[10010], t[2005]; int cnt[10010]; long long cross(point a, point b) { return a.x * b.y - a.y * b.x; } int side(point a) { if(a.y > 0 || (a.y == 0 && a.x >= 0)) return 0; else return 1; } bool cmp(point a, point b) { if(side(a) == side(b)) { return cross(a, b) > 0; } else { return side(a) < side(b); } } int main(int argc, char const *argv[]) { int w, h; point s; scanf("%d %d", &w, &h); scanf("%lld %lld", &s.x, &s.y); int C; scanf("%d", &C); for(int i = 1; i <= C; i++) { scanf("%lld %lld", &c[i].x, &c[i].y); } int N; scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%lld %lld", &t[i].x, &t[i].y); } for(int i = 1; i <= N; i++) { vector <point> v; for(int j = 1; j <= C; j++) { point p = c[j] - t[i]; p.id = j; v.emplace_back(p); } for(int j = 1; j <= N; j++) { if(j == i) continue; point p = t[i] - t[j]; p.id = 0; v.emplace_back(p); } point p = s - t[i]; p.id = -1; v.emplace_back(p); sort(v.begin(), v.end(), cmp); int pos = 0; for(int j = 0; j < v.size(); j++) { if(v[j].id < 0) { pos = j; break; } } int cur = pos; int sz = v.size(); while(v[cur].id != 0) { if(v[cur].id > 0) { cnt[v[cur].id] += 1; } cur = (cur + 1) % sz; } cur = pos; while(v[cur].id != 0) { if(v[cur].id > 0) { cnt[v[cur].id] += 1; } cur = (sz + cur - 1) % sz; } } int ans = 0; for(int i = 1; i <= C; i++) { if(cnt[i] == N) { ++ans; } } printf("%d\n", ans); for(int i = 1; i <= C; i++) { if(cnt[i] == N) { printf("%d ", i); } } if(ans) printf("\n"); return 0; }

Compilation message (stderr)

fangorn.cpp: In function 'int main(int, const char**)':
fangorn.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < v.size(); j++) {
                  ~~^~~~~~~~~~
fangorn.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &w, &h);
  ~~~~~^~~~~~~~~~~~~~~~~
fangorn.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &s.x, &s.y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
  ~~~~~^~~~~~~~~~
fangorn.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &c[i].x, &c[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
fangorn.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &t[i].x, &t[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...