제출 #793218

#제출 시각아이디문제언어결과실행 시간메모리
793218peijarThe Forest of Fangorn (CEOI14_fangorn)C++17
100 / 100
2745 ms1252 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...