oj.uz

Submission #567121

# Submission time Handle Problem Language Result Execution time Memory
567121 2022-05-23T08:13:21 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
0 / 100
 768 ms 1272 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;

struct Vector {
  ll x;
  ll y;
};

Vector operator + (Vector a, Vector b) {
  return { a.x + b.x, a.y + b.y };
}

Vector operator - (Vector a, Vector b) {
  return { a.x - b.x, a.y - b.y };
}

Vector operator * (Vector a, ll b) {
  return { a.x * b, a.y * b };
}


Vector operator * (ll b, Vector a) {
  return { a.x * b, a.y * b };
}


Vector readVector() {
  int x, y;
  cin >> x >> y;
  return { x, y };
}

const int N = 2000 + 7;
const int C = 10000 + 7;

int w, h;
int n, c;
int cnt_good[C];
Vector camps[C];
Vector trees[N];
Vector myself;


bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
  return atan2((ld)a.first.y, (ld)a.first.x) < atan2((ld)b.first.y, (ld)b.first.x);
}

int get_type(Vector a) {

  if (a.x == w) return 0;
  if (a.y == h) return 1;
  if (a.x == 0) return 2;
  if (a.y == 0) return 3;
}

bool cmpOnRect(int i, int j) {
  Vector a = camps[i];
  Vector b = camps[j];

  int type_a = get_type(a);
  int type_b = get_type(b);
  if (type_a != type_b) return type_a < type_b;
  int type = type_a;

  if (type == 0) {
    return a.y < b.y;
  }
  if (type == 1) {
    return a.x > b.x;
  }
  if (type == 2) {
    return a.y > b.y;
  }
  if (type == 3) {
    return a.x < b.x;
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> w >> h;
  myself = readVector();

  vector<int> inds;

  cin >> c;
  for (int i = 1; i <= c; i++) {
    camps[i] = readVector();
    inds.push_back(i);
  }
  sort(inds.begin(), inds.end(), cmpOnRect);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    trees[i] = readVector();
  }
  for (int tid = 1; tid <= n; tid++) {
    Vector origin = trees[tid];
    vector<pair<Vector, int>> events;
    for (int i = 1; i <= n; i++) {
      if (i == tid) continue;
      Vector delta = trees[i] - origin;
      events.push_back({ {-delta.x,-delta.y}, -1 });
    }
    events.push_back({ myself - origin, 0 });
    auto cop_events = events;

    ld minAng = (ld)1e18;
    int start = -1;

    for (int P = 0; P < c; P++) {
      int i = inds[P];
      Vector vec = camps[i] - origin;
      ld ang = atan2(vec.y, vec.x);
      if (ang < minAng) {
        minAng = ang;
        start = P;
      }
    }

    vector<pair<Vector, int>> cps;
    for (int l = 0; l < c; l++) {
      int i = inds[(start + l) % c];
      cps.push_back({ camps[i] - origin, i });
    }

    vector<pair<Vector, int>> so;

    int p1 = 0, p2 = 0;
    while (p1 < (int)cps.size() && p2 < (int)cop_events.size()) {
      if (cmp(cps[p1], cop_events[p2])) {
        so.push_back(cps[p1++]);
      }
      else {
        so.push_back(cop_events[p2++]);
      }
    }
    while (p1 < (int)cps.size()) {
      so.push_back(cps[p1++]);
    }

    while (p2 < (int)cop_events.size()) {
      so.push_back(cop_events[p2++]);
    }

    events = so;
    int p0 = 0;
    while (events[p0].second != 0) p0++;

    int l = p0, r = p0, sz = (int)events.size();

    while (events[(l + sz - 1) % sz].second != -1) l = (l + sz - 1) % sz;
    while (events[(r + 1) % sz].second != -1) r = (r + 1) % sz;

    for (int j = l; j != (r + 1) % sz; j = (j + 1) % sz) {
      if (events[j].second > 0) {
        cnt_good[events[j].second]++;
      }
    }
  }
  vector<int> sol;
  for (int i = 1; i <= c; i++) {
    if (cnt_good[i] == n) {
      sol.push_back(i);
    }
  }
  cout << (int)sol.size() << "\n";
  for (auto& i : sol) {
    cout << i << " ";
  }
  cout << "\n";
}

Compilation message

fangorn.cpp: In function 'int get_type(Vector)':
fangorn.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 376 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 4 ms 340 KB Output isn't correct
11 Correct 5 ms 340 KB Output is correct
12 Incorrect 5 ms 340 KB Output isn't correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 768 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -