Submission #567181

#	Time	Username	Problem	Language	Result	Execution time	Memory
567181		600Mihnea	The Forest of Fangorn (CEOI14_fangorn)	C++17	15 / 100	1269 ms	976 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Vector {
  int x;
  int y;
};

ll f(Vector a, Vector b) {
  return (a.x - b.x) * (ll) (a.y + b.y);
}

ll f(Vector a, Vector b, Vector c) {
  return f(a, b) + f(b, c) + f(c, a);
}

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;

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;
  }
}


int get_cadran(Vector a) {
  if (a.x >= 0) {
    if (a.y > 0) {
      return 2;
    } else {
      return 1;
    }
  } else {
    if (a.y < 0) {
      return 0;
    } else {
      return 3;
    }
  }
}

bool cmp_Vector(Vector a, Vector b) {
  int cadran_a = get_cadran(a);
  int cadran_b = get_cadran(b);
  if (cadran_a != cadran_b) {
    return cadran_a < cadran_b;
  }
  return (f({0, 0}, a, b) > 0);
}

bool cmp2(pair<Vector, int> a, pair<Vector, int> b) {
  return cmp_Vector(a.first, b.first);
}

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;

    int start = 0;

    for (int P = 1; P < c; P++) {
      int i = inds[P];
      if (cmp_Vector(camps[i] - origin, camps[start] - origin)) {
        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 });
    }



    sort(cop_events.begin(), cop_events.end(), cmp2);


    vector<pair<Vector, int>> so;

    int p1 = 0, p2 = 0;
    while (p1 < (int)cps.size() && p2 < (int)cop_events.size()) {
      if (cmp2(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 (stderr)

fangorn.cpp: In function 'Vector operator*(Vector, ll)':
fangorn.cpp:29:16: warning: narrowing conversion of '(((ll)a.Vector::x) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   29 |   return { a.x * b, a.y * b };
      |            ~~~~^~~
fangorn.cpp:29:25: warning: narrowing conversion of '(((ll)a.Vector::y) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   29 |   return { a.x * b, a.y * b };
      |                     ~~~~^~~
fangorn.cpp: In function 'Vector operator*(ll, Vector)':
fangorn.cpp:34:16: warning: narrowing conversion of '(((ll)a.Vector::x) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   34 |   return { a.x * b, a.y * b };
      |            ~~~~^~~
fangorn.cpp:34:25: warning: narrowing conversion of '(((ll)a.Vector::y) * b)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   34 |   return { a.x * b, a.y * b };
      |                     ~~~~^~~
fangorn.cpp: In function 'int get_type(Vector)':
fangorn.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

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