# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
577649 |
2022-06-15T07:26:48 Z |
tengiz05 |
Roads (CEOI20_roads) |
C++17 |
|
90 ms |
2768 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(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;
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);
X1[i] = x1;
Y1[i] = y1;
X2[i] = x2;
Y2[i] = y2;
}
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;
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());
if (!bad(L.r)) {
cout << x << " " << y << " " << L.r.first << " " << L.r.second << "\n";
} else if (!bad(R.l)) {
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);
s.erase(s.lower_bound(Line(X1[-i], Y1[-i], x, y)));
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Failed |
90 ms |
2736 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
12 ms |
1076 KB |
Output is correct |
5 |
Correct |
21 ms |
1744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
11 ms |
1060 KB |
Output is correct |
5 |
Correct |
31 ms |
1736 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Failed |
2 ms |
340 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
12 ms |
1068 KB |
Output is correct |
5 |
Correct |
25 ms |
1800 KB |
Output is correct |
6 |
Failed |
1 ms |
212 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
280 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
19 ms |
1348 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Failed |
2 ms |
340 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Failed |
78 ms |
2768 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
3 |
Halted |
0 ms |
0 KB |
- |