Submission #567172

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

fangorn

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;

struct Vector {
  ll x;
  ll 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;

const ld eps=1e-14;

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

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

ld get_f(pair<ld, ld> a, pair<ld, ld> b) {
  return (a.first - b.first) * (a.second + b.second);
}

ld get_f(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> c) {
  return get_f(a, b) + get_f(b, c) + get_f(c, a);
}

int get_cadran(pair<ld, ld> a) {
  if (a.first >= 0) {
    if (a.second >= 0) {
      return 0;
    } else {
      return 3;
    }
  } else {
    if (a.second <= 0) {
      return 2;
    } else {
      return 1;
    }
  }
}

int tr_cadran(int c) {
  return (c + 2) % 4;
}

bool cmp_pld(pair<ld, ld> a, pair<ld, ld> b) {
  int cadran_a = get_cadran(a);
  int cadran_b = get_cadran(b);
  cadran_a = tr_cadran(cadran_a);
  cadran_b = tr_cadran(cadran_b);
  if (cadran_a != cadran_b) {
    return cadran_a < cadran_b;
  }
  return (get_f(pair<ld, ld> (0, 0), a, b) > 0);
}



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

bool cmp_Vector(Vector a, Vector b) {
  int cadran_a = get_cadran(a);
  int cadran_b = get_cadran(b);
  cadran_a = tr_cadran(cadran_a);
  cadran_b = tr_cadran(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);

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


  if (0) {
    const int cntc=16;

    vector<pair<ld, ld>> all;
    for (int j=0;j<cntc;j++) {
      const ld pi=(ld)2*acos((ld)0);
      ld x=cos((ld)j/cntc*(2*pi));
      ld y=sin((ld)j/cntc*(2*pi));
      all.push_back({x, y});
     // cout<<x<<" "<<y<<" P"<<j<<"\n";
    }
    sort(all.begin(), all.end(), cmp_pld);
    for (int i = 0; i < (int) all.size(); i++) {
      ld x = all[i].first, y = all[i].second;
      cout << x << " " << y << " P" << i << "\n";
    }
    exit(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();
  }

  bool is = (n >= 1500);


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



    if (is) {
      continue;
    }
    auto cop_events2 = cop_events;

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

    if (0) {
      for (auto &it : cop_events) cout << it.second << " "; cout << "\n";
      for (auto &it : cop_events2) cout << it.second << " "; cout << "\n";
      cout << "\n";
    }

    if (1 && (tid == -3)) {
      int cnt = 1;
      cout << 0 << " " << 0 << " O\n";
      for (auto &it : cop_events2) {
        cout << it.first.x << " " << it.first.y << " P" << cnt++ << "\n";
      }
      cout << "-------------\n";

      return 0;
    }

    if (tid == 1 || tid == 2 || 1) {
      cop_events = cop_events2;
    }

    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 (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:252:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  252 |       for (auto &it : cop_events) cout << it.second << " "; cout << "\n";
      |       ^~~
fangorn.cpp:252:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  252 |       for (auto &it : cop_events) cout << it.second << " "; cout << "\n";
      |                                                             ^~~~
fangorn.cpp:253:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  253 |       for (auto &it : cop_events2) cout << it.second << " "; cout << "\n";
      |       ^~~
fangorn.cpp:253:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  253 |       for (auto &it : cop_events2) cout << it.second << " "; cout << "\n";
      |                                                              ^~~~
fangorn.cpp: In function 'int get_type(Vector)':
fangorn.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^

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