Submission #588032

#TimeUsernameProblemLanguageResultExecution timeMemory
588032MilosMilutinovicPlanine (COCI21_planine)C++14
0 / 110
4 ms852 KiB
/** * author: wxhtzdy * created: 02.07.2022 16:49:56 **/ #include <bits/stdc++.h> using namespace std; #define int long long signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, h; cin >> n >> h; vector<int> x(n), y(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } vector<pair<int, int>> ev; for (int i = 2; i < n - 1; i += 2) { ev.emplace_back(i, 0); ev.emplace_back(i, 1); } sort(ev.begin(), ev.end(), [&](pair<int, int> a, pair<int, int> b) { int xa = x[a.first]; int xb = x[b.first]; int pa = (a.second == 0 ? x[a.first - 1] : x[a.first + 1]) - x[a.first]; int pb = (b.second == 0 ? x[b.first - 1] : x[b.first + 1]) - x[b.first]; int qa = (a.second == 0 ? y[a.first - 1] : y[a.first + 1]) - y[a.first]; int qb = (b.second == 0 ? y[b.first - 1] : y[b.first + 1]) - y[b.first]; double new_xa = xa + h * ((double) pa / (double) qa); double new_xb = xb + h * ((double) pb / (double) qb); // xa + h * (pa / qa) < xb + h * (pb / qb) // xa - xb < h * (pb / qb - pa / qa) // (xa - xb) / h < pb / qb - pa / qa // (xa - xb) / h < (pb * qa - pa * qb) / qa * qb // (xa - xb) * (qa * qb) < (pb * qa - pa * qb) * h long long dx = xa - xb; long long pq = qa * 1LL * qb; long long qp = pb * 1LL * qa - pa * 1LL * qb; long long L = dx * pq; long long R = qp * h; if (new_xa == new_xb) { return a.second < b.second; } else { return new_xa < new_xb; } }); int ans = 0; set<int> alive; for (auto& e : ev) { if (e.second == 0) { alive.insert(e.first); } else { if (alive.find(e.first) == alive.end()) { continue; } alive.clear(); ans += 1; } } cout << ans << '\n'; return 0; }

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:43:15: warning: unused variable 'L' [-Wunused-variable]
   43 |     long long L = dx * pq;
      |               ^
Main.cpp:44:15: warning: unused variable 'R' [-Wunused-variable]
   44 |     long long R = qp * h;
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...