Submission #577635

#TimeUsernameProblemLanguageResultExecution timeMemory
577635tengiz05Roads (CEOI20_roads)C++17
0 / 100
22 ms4500 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; constexpr int inf = 1E9; int Time; struct Line { int x, y; double s; pair<int, int> l, r; Line(int x1, int y1, int x2, int y2) { x = x1; y = y1; if (x2 - x1 == 0) { s = 0; } else { s = 1. * (y2 - y1) / (x2 - x1); } l = r = {x1, y1}; } double at() { return y + (Time - x) * s; } }; double at(const Line x) { return x.y + (Time - x.x) * x.s; } inline bool operator<(const Line &a, const Line &b) { if (at(a) - at(b) < -1e-9) return true; return false; } bool bad(const pair<int, int> &x) { return abs(x.first) == inf; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<tuple<int, int, int>> events; vector<int> X1(n + 2), Y1(n + 2), X2(n + 2), Y2(n + 2); for (int i = 1; i <= n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; X1[i] = x1; Y1[i] = y1; X2[i] = x2; Y2[i] = y2; if (x1 > x2) { swap(x1, x2); swap(y1, y2); } else if (x1 == x2 && y1 > y2) { swap(y1, y2); } events.emplace_back(x1, y1, i); events.emplace_back(x2, y2, -i); } sort(events.begin(), events.end()); set<Line> s; s.insert(Line(-inf, -inf, inf, -inf)); s.insert(Line(-inf, inf, inf, inf)); for (auto [x, y, i] : events) { Time = x; // cerr << "Checking " << x << " " << y << ", " << i << "\n"; // for (auto x : s) { // cout << at(x) << " : "; // cout << x.x << " " << x.y << "\n"; // } if (i > 0) { auto L = *prev(s.upper_bound(Line(x, y, x, y))); auto R = *s.upper_bound(Line(x, y, x, y)); assert(s.upper_bound(Line(x, y, x, y)) != s.end()); // cout << at(Line(x, y, x, y)); // cout << "this is it " << R.x << " " << R.y << "\n"; if (!bad(L.r)) { // cout << "HMM\n"; cout << x << " " << y << " " << L.r.first << " " << L.r.second << "\n"; } else if (!bad(R.l)) { // cout << "SD\n"; cout << x << " " << y << " " << R.l.first << " " << R.l.second << "\n"; } else { } s.insert(Line(x, y, X2[i], Y2[i])); } else { auto L = *prev(s.lower_bound(Line(x, y, x, y))); auto R = *s.upper_bound(Line(x, y, x, y)); L.r = {x, y}; R.l = {x, y}; s.erase(L); s.erase(R); s.insert(L); s.insert(R); // auto c = *s.lower_bound(Line(X1[-i], Y1[-i], x, y)); // cout << at(Line(X1[-i], Y1[-i], x, y)) << ",," << X1[-i] << " " << Y1[-i] << "\n"; // cout << " we are about to end this man's whole career: " << c.x << " " << c.y << "\n"; s.erase(s.lower_bound(Line(X1[-i], Y1[-i], x, y))); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...