Submission #567115

#	Time	Username	Problem	Language	Result	Execution time	Memory
567115		600Mihnea	The Forest of Fangorn (CEOI14_fangorn)	C++17	50 / 100	3068 ms	1152 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct Vector {
  ll x;
  ll y;



  /**Vector() : x(0), y(0) {
  }

  Vector(ll x, ll y) : x(x), y(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 cmpByAngle(Vector a, Vector b) {
  return atan2((ld)a.y, (ld)a.x) < atan2((ld)b.y, (ld)b.x);
}

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

int get_type(Vector a) {
  assert(a.x == 0 || a.x == w || a.y == 0 || a.y == h);

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

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) {
    assert(a.y != b.y);
    return a.y < b.y;
  }
  if (type == 1) {
    assert(a.x != b.x);
    return a.x > b.x;
  }
  if (type == 2) {
    assert(a.y != b.y);
    return a.y > b.y;
  }
  if (type == 3) {
    assert(a.x != b.x);
    return a.x < b.x;
  }
  assert(0);
}

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

  /// freopen ("input.txt", "r", stdin);

  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++) {
    /// tid=3;
    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;
      /// trees[i] - origin = delta
      /// trees[i] = origin + delta
      events.push_back({ {-delta.x,-delta.y}, -1 });
    }
    events.push_back({ myself - origin, 0 });
    auto cop_events = events;
    assert((int)inds.size() == c);

    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;
      }
    }
    assert(start != -1);

    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(), cmp);
    sort(cps.begin(), cps.end(), cmp);
    vector<pair<Vector, int>> so;

    /// so = mrg(cps, cop_events)

    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;
    /**cout<<"\t\t\t\t";
    for (int i=1;i<=c;i++) {
      cout<<cnt_good[i]<<" ";
    }
    cout<<"\n";
    events=so;**/
    int cox = 0;
    /*cout<<"0 0 O\n";
    for (auto &it : events) {
      cox++;

      cout<<it.first.x<<" "<<it.first.y<<" P";
      if (it.second==-1) {
        cout<<"x";
      }else{
        cout<<it.second;

      }
      cout<<"\n";
    }*/
    int p0 = 0;
    while (events[p0].second != 0) p0++;
    assert(p0 < (int)events.size());
    assert(events[p0].second == 0);
    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 (auto &j : events) {
      cout<<j.second<<" ";
    }
    cout<<" -------> ";

    cout<<" = "<<l<<" and "<<r<<"\n";
*/
    for (int j = l; j != (r + 1) % sz; j = (j + 1) % sz) {
      assert(events[j].second >= 0);
      if (events[j].second > 0) {
        assert(1 <= events[j].second && events[j].second <= c);
        cnt_good[events[j].second]++;
      }
    }
    ///return 0;
  }
  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 'int main()':
fangorn.cpp:188:9: warning: unused variable 'cox' [-Wunused-variable]
  188 |     int cox = 0;
      |         ^~~

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