This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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() {}
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-10)
return true;
return false;
}
bool bad(const pair<int, int> &x) {
return abs(x.first) == inf;
}
Line p[100005];
struct Info {
int x;
Info(int x) : x(x) {}
};
bool operator<(const Info &a, const Info &b) {
return p[a.x] < p[b.x];
}
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<Info> s;
p[0] = Line(-inf, -inf, inf, -inf);
p[n + 1] = Line(-inf, inf, inf, inf);
for (int i = 1; i <= n; i++) {
p[i] = Line(X1[i], Y1[i], X2[i], Y2[i]);
}
s.insert(Info(0));
s.insert(Info(n + 1));
for (auto [x, y, i] : events) {
Time = x;
if (i > 0) {
auto &L = p[prev(s.upper_bound(Info(i)))->x];
auto &R = p[s.upper_bound(Info(i))->x];
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 {
}
L.r = {x, y};
R.l = {x, y};
s.insert(Info(i));
} else {
i = -i;
auto &L = p[prev(s.lower_bound(Info(i)))->x];
auto &R = p[next(s.lower_bound(Info(i)))->x];
L.r = {x, y};
R.l = {x, y};
s.erase(Info(i));
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |