QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#67562 | #949. Roads | alpha1022 | 100 ✓ | 128ms | 9788kb | C++23 | 1.6kb | 2022-12-10 17:27:04 | 2022-12-10 17:27:05 |
Judging History
answer
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int inf = 0x3f3f3f3f;
int n;
struct Point {
int x, y;
inline Point(int x = 0, int y = 0): x(x), y(y) {}
inline bool operator<(const Point &o) const {
return x != o.x ? x < o.x : y < o.y;
}
};
struct Segment {
Point s, t;
inline Segment(Point s = Point(), Point t = Point()): s(s), t(t) {}
inline double get(int x) const {
if (s.x == t.x)
return s.y;
return s.y + (double)(t.y - s.y) / (t.x - s.x) * (x - s.x);
}
inline bool operator<(const Segment &o) const {
int x = max(s.x, o.s.x);
return get(x) < o.get(x);
}
} a[N + 5];
vector<pair<Point, int>> p;
map<Segment, Point> vis;
int main() {
//freopen("network.in", "r", stdin), freopen("network.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d%d", &a[i].s.x, &a[i].s.y, &a[i].t.x, &a[i].t.y);
if (a[i].t < a[i].s)
swap(a[i].s, a[i].t);
p.emplace_back(a[i].s, i), p.emplace_back(a[i].t, i);
}
sort(p.begin(), p.end());
vis.emplace(Segment(Point(-inf, -inf), Point(-inf, inf)), Point());
for (int i = 0; i < p.size(); ++i) {
Point x;
int id;
tie(x, id) = p[i];
if (x < a[id].t) {
auto it = --vis.emplace(a[id], x).first;
if (i)
printf("%d %d %d %d\n", it->second.x, it->second.y, x.x, x.y);
it->second = x;
} else {
auto it = vis.find(a[id]);
prev(it)->second = x;
vis.erase(it);
}
}
}
詳細信息
Subtask #1:
score: 0
Accepted
Test #1:
score: 0
Accepted
time: 4ms
memory: 4736kb
Test #2:
score: 0
Accepted
time: 18ms
memory: 5940kb
Subtask #2:
score: 15
Accepted
Test #3:
score: 15
Accepted
time: 0ms
memory: 4600kb
Test #4:
score: 0
Accepted
time: 3ms
memory: 4744kb
Test #5:
score: 0
Accepted
time: 4ms
memory: 4776kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 4716kb
Test #7:
score: 0
Accepted
time: 27ms
memory: 5116kb
Subtask #3:
score: 15
Accepted
Test #8:
score: 15
Accepted
time: 4ms
memory: 4576kb
Test #9:
score: 0
Accepted
time: 3ms
memory: 4752kb
Test #10:
score: 0
Accepted
time: 4ms
memory: 4696kb
Test #11:
score: 0
Accepted
time: 15ms
memory: 4700kb
Test #12:
score: 0
Accepted
time: 128ms
memory: 7288kb
Subtask #4:
score: 15
Accepted
Test #13:
score: 15
Accepted
time: 1ms
memory: 4600kb
Test #14:
score: 0
Accepted
time: 3ms
memory: 4692kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 4776kb
Test #16:
score: 0
Accepted
time: 11ms
memory: 4772kb
Test #17:
score: 0
Accepted
time: 51ms
memory: 5840kb
Subtask #5:
score: 15
Accepted
Test #18:
score: 15
Accepted
time: 2ms
memory: 4664kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 4644kb
Test #20:
score: 0
Accepted
time: 3ms
memory: 4648kb
Test #21:
score: 0
Accepted
time: 3ms
memory: 4668kb
Test #22:
score: 0
Accepted
time: 1ms
memory: 4656kb
Test #23:
score: 0
Accepted
time: 3ms
memory: 4664kb
Test #24:
score: 0
Accepted
time: 4ms
memory: 4700kb
Test #25:
score: 0
Accepted
time: 3ms
memory: 4584kb
Test #26:
score: 0
Accepted
time: 7ms
memory: 4936kb
Test #27:
score: 0
Accepted
time: 2ms
memory: 4720kb
Test #28:
score: 0
Accepted
time: 5ms
memory: 4808kb
Subtask #6:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #29:
score: 40
Accepted
time: 64ms
memory: 7808kb
Test #30:
score: 0
Accepted
time: 76ms
memory: 8696kb
Test #31:
score: 0
Accepted
time: 2ms
memory: 4692kb
Test #32:
score: 0
Accepted
time: 69ms
memory: 5736kb
Test #33:
score: 0
Accepted
time: 79ms
memory: 5808kb
Test #34:
score: 0
Accepted
time: 103ms
memory: 7352kb
Test #35:
score: 0
Accepted
time: 115ms
memory: 7280kb
Test #36:
score: 0
Accepted
time: 108ms
memory: 9788kb
Extra Test:
score: 0
Extra Test Passed