Submission #793218

#	Time	Username	Problem	Language	Result	Execution time	Memory
793218		peijar	The Forest of Fangorn (CEOI14_fangorn)	C++17	100 / 100	2745 ms	1252 KiB

fangorn

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <typename T> struct Point {
  T x, y;

  Point() : x(0), y(0) {}

  Point(T _x, T _y) : x(_x), y(_y) {}

  Point operator+(const Point other) const {
    return Point(x + other.x, y + other.y);
  }

  Point operator-(const Point other) const {
    return Point(x - other.x, y - other.y);
  }

  Point operator*(const T lambda) const {
    return Point(x * lambda, y * lambda);
  }

  Point operator/(const T lambda) const {
    return Point(x / lambda, y / lambda);
  }

  bool operator<(const Point &other) const {
    return tie(x, y) < tie(other.x, other.y);
  }
  bool operator==(const Point &other) const {
    return tie(x, y) == tie(other.x, other.y);
  }
  bool operator>(const Point &other) const { return other < *this; }
  bool operator!=(const Point &other) const { return !(*this == other); }
  bool operator<=(const Point &other) const { return !(other < *this); }
  bool operator>=(const Point &other) const { return other <= *this; }

  friend ostream &operator<<(ostream &out, const Point &a) {
    return out << a.x << " " << a.y;
  }
  friend istream &operator>>(istream &in, Point &a) { return in >> a.x >> a.y; }
  friend T dot(const Point a, const Point b) { return a.x * b.x + a.y * b.y; }

  friend T cross(const Point a, const Point b) { return a.x * b.y - a.y * b.x; }

  friend T dis2(const Point a, const Point b) { return dot(b - a, b - a); }
};

using pt = Point<int>;

struct Angle {
  int x, y;
  int t;
  Angle(int x, int y, int t = 0) : x(x), y(y), t(t) {}
  Angle operator-(Angle b) const { return {x - b.x, y - b.y, t}; }
  int half() const {
    assert(x || y);
    return y < 0 || (y == 0 && x < 0);
  }
  Angle t90() const { return {-y, x, t + (half() && x >= 0)}; }
  Angle t180() const { return {-x, -y, t + half()}; }
  Angle t360() const { return {x, y, t + 1}; }
};
bool operator<(Angle a, Angle b) {
  // add a . dist2 () and b . dist2 () to also compare distances
  return make_tuple(a.t, a.half(), a.y * (int)b.x) <
         make_tuple(b.t, b.half(), a.x * (int)b.y);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int w, h;
  cin >> w >> h;
  pt init;
  cin >> init;

  int nbCamps;
  cin >> nbCamps;
  vector<pt> camps(nbCamps);
  for (pt &p : camps)
    cin >> p;
  int nbArbres;
  cin >> nbArbres;
  vector<pt> arbres(nbArbres);

  for (pt &p : arbres)
    cin >> p;

  vector<int> sol(nbCamps);
  iota(sol.begin(), sol.end(), 0);
  for (int i = 0; i < nbArbres; ++i) {
    vector<Angle> rays;
    for (int j = 0; j < nbArbres; ++j)
      if (i != j) {
        pt p = arbres[i] - arbres[j];
        rays.emplace_back(p.x, p.y);
        rays.emplace_back(p.x, p.y, 1);
        rays.emplace_back(p.x, p.y, -1);
      }
    sort(rays.begin(), rays.end());

    vector<int> nxtSol;
    pt r = init - arbres[i];
    Angle rayInit(r.x, r.y);
    int u = lower_bound(rays.begin(), rays.end(), rayInit) - rays.begin();
    for (int c : sol) {
      pt p = camps[c] - arbres[i];
      Angle ray(p.x, p.y);
      int v = lower_bound(rays.begin(), rays.end(), ray) - rays.begin();
      while (u >= nbArbres - 1)
        u -= nbArbres - 1;
      while (v >= nbArbres - 1)
        v -= nbArbres - 1;
      if (u == v)
        nxtSol.push_back(c);
    }
    sol = nxtSol;
  }

  cout << sol.size() << endl;
  for (int x : sol)
    cout << x + 1 << ' ';
  cout << endl;
}

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