# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
577635 |
2022-06-15T07:01:37 Z |
tengiz05 |
Roads (CEOI20_roads) |
C++17 |
|
22 ms |
4500 KB |
#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 time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
20 ms |
4500 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
1 ms |
448 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Runtime error |
22 ms |
4480 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |