제출 #588500

#제출 시각아이디문제언어결과실행 시간메모리
588500MilosMilutinovicPlanine (COCI21_planine)C++14
110 / 110
244 ms54596 KiB
/** * author: wxhtzdy * created: 03.07.2022 13:33:18 **/ #include <bits/stdc++.h> using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif struct Frac { long long p, q; }; bool operator < (Frac a, Frac b) { return a.p * b.q < b.p * a.q; } struct Point { int x, y; }; int orientation(Point a, Point b, Point c) { long long prod = (b.y - a.y) * 1LL * (c.x - b.x) - (b.x - a.x) * 1LL * (c.y - b.y); return (prod == 0 ? 0 : (prod > 0 ? 1 : -1)); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, h; cin >> n >> h; vector<Point> a(n); for (int i = 0; i < n; i++) { cin >> a[i].x >> a[i].y; } vector<Point> L(n); { vector<Point> hull(1, a[0]); for (int i = 1; i < n; i++) { while ((int) hull.size() > 1 && orientation(hull.rbegin()[1], hull.rbegin()[0], a[i]) == -1) { hull.pop_back(); } L[i] = hull.back(); hull.push_back(a[i]); } } vector<Point> R(n); { vector<Point> hull(1, a[n - 1]); for (int i = n - 2; i >= 0; i--) { while ((int) hull.size() > 1 && orientation(a[i], hull.rbegin()[0], hull.rbegin()[1]) == -1) { hull.pop_back(); } R[i] = hull.back(); hull.push_back(a[i]); } } for (int i = 2; i < n - 1; i += 2) { debug(i, L[i].x, L[i].y); debug(i, R[i].x, R[i].y); } vector<pair<Frac, Frac>> ev; for (int i = 2; i < n - 1; i += 2) { Frac fL, fR; fL.p = a[i].x * 1LL * (L[i].y - a[i].y) + (h - a[i].y) * 1LL * (L[i].x - a[i].x); fL.q = L[i].y - a[i].y; fR.p = a[i].x * 1LL * (R[i].y - a[i].y) + (h - a[i].y) * 1LL * (R[i].x - a[i].x); fR.q = R[i].y - a[i].y; ev.emplace_back(fL, fR); } sort(ev.begin(), ev.end(), [&](pair<Frac, Frac> a, pair<Frac, Frac> b) { return a.second < b.second; }); Frac lst; int ans = 0; for (int i = 0; i < (int) ev.size(); i++) { if (i == 0 || lst < ev[i].first) { ans += 1; lst = ev[i].second; } } cout << ans << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
Main.cpp:98:5: note: in expansion of macro 'debug'
   98 |     debug(i, L[i].x, L[i].y);
      |     ^~~~~
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
Main.cpp:99:5: note: in expansion of macro 'debug'
   99 |     debug(i, R[i].x, R[i].y);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...