#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
struct Usecka{
pii a,b;
int idx;
};
bool stejny(Usecka a, Usecka b){
if ((a.a.x == b.a.x && a.a.y == b.a.y && a.b.x == b.b.x && a.b.y == b.b.y) || (a.a.x == b.b.x && a.a.y == b.b.y && a.b.x == b.a.x && a.b.y == b.a.y)){
return true;
}
return false;
}
bool comp(const Usecka& l, const Usecka& r){
if ((l.a.x == r.a.x && l.a.y == r.a.y && l.b.x == r.b.x && l.b.y == r.b.y) || (l.a.x == r.b.x && l.a.y == r.b.y && l.b.x == r.a.x && l.b.y == r.a.y)){
return false;
}
bool prohozeny = false;
Usecka u;
pii b;
if (min(l.a.x,l.b.x) >= min(r.a.x,r.b.x) && min(l.a.x,l.b.x) <= max(r.a.x,r.b.x)){
b = min(l.a, l.b);
u = r;
} else {
b = min(r.a, r.b);
u = l;
prohozeny = true;
}
if (u.a.x == u.b.x || b.x == u.a.x){
return prohozeny^(u.a.y>b.y);
} else {
long double ynko = u.a.y + ((long double)(u.b.y-u.a.y)*(b.x-u.a.x))/((long double)(u.b.x-u.a.x));
return prohozeny^(ynko>b.y);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; cin >> n;
vector<Usecka> points(2*n);
for (int i = 0; i<n; i++){
int a,b,c,d; cin >> a >> b >> c >> d;
points[2*i] = {{a,b},{c,d},i};
points[2*i+1] = {{c,d},{a,b},i};
}
sort(points.begin(), points.end(), [](const Usecka& l, const Usecka &r){
return (l.a.x < r.a.x) || (l.a.x == r.a.x && l.a.y < r.a.y);
});
vector<pii> nad(n, {INT_MAX,INT_MAX});
vector<pii> pod(n, {INT_MAX,INT_MAX});
pii last_deleted = {INT_MAX,INT_MAX};
set<Usecka, decltype(&comp)> usecky(&comp);
usecky.insert(points[0]);
nad[points[0].idx] = points[0].a;
pod[points[0].idx] = points[0].a;
for (int i = 1; i<2*n; i++){
auto it = usecky.lower_bound(points[i]);
if (it != usecky.end() && stejny(*it, points[i])){
if (it != usecky.begin()){
it--;
nad[it->idx] = points[i].a;
it++;
}
it++;
if (it != usecky.end()){
pod[it->idx] = points[i].a;
}
it--;
last_deleted = points[i].a;
usecky.erase(it);
} else {
if (usecky.size() == 0){
cout << points[i].a.x << " " << points[i].a.y << " " << last_deleted.x << " " << last_deleted.y << endl;
} else {
if (it != usecky.end()){
cout << points[i].a.x << " " << points[i].a.y << " " << pod[it->idx].x << " " << pod[it->idx].y << endl;
} else {
it--;
cout << points[i].a.x << " " << points[i].a.y << " " << nad[it->idx].x << " " << nad[it->idx].y << endl;
it++;
}
}
if (it != usecky.end()){
pod[it->idx] = points[i].a;
}
if (it != usecky.begin()){
it--;
nad[it->idx] = points[i].a;
it++;
}
nad[points[i].idx]=points[i].a;
pod[points[i].idx]=points[i].a;
usecky.insert(points[i]);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
75 ms |
3364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
17 ms |
1116 KB |
Output is correct |
5 |
Correct |
34 ms |
2132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
19 ms |
1280 KB |
Output is correct |
5 |
Correct |
34 ms |
2128 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
18 ms |
1116 KB |
Output is correct |
10 |
Correct |
213 ms |
8788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
19 ms |
1116 KB |
Output is correct |
5 |
Correct |
32 ms |
2024 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
344 KB |
Output is correct |
9 |
Correct |
16 ms |
1116 KB |
Output is correct |
10 |
Correct |
80 ms |
4436 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
17 ms |
1208 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
17 ms |
1112 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
16 ms |
1112 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
7 ms |
604 KB |
Output is correct |
23 |
Correct |
7 ms |
600 KB |
Output is correct |
24 |
Correct |
17 ms |
860 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
73 ms |
3164 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
16 ms |
1112 KB |
Output is correct |
7 |
Correct |
32 ms |
2128 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
17 ms |
1116 KB |
Output is correct |
12 |
Correct |
207 ms |
8784 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
344 KB |
Output is correct |
16 |
Correct |
16 ms |
1116 KB |
Output is correct |
17 |
Correct |
82 ms |
4436 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
8 ms |
600 KB |
Output is correct |
27 |
Correct |
7 ms |
604 KB |
Output is correct |
28 |
Correct |
14 ms |
1000 KB |
Output is correct |
29 |
Correct |
136 ms |
6484 KB |
Output is correct |
30 |
Correct |
208 ms |
9044 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
138 ms |
5956 KB |
Output is correct |
33 |
Correct |
144 ms |
5960 KB |
Output is correct |
34 |
Correct |
183 ms |
7764 KB |
Output is correct |
35 |
Correct |
193 ms |
8084 KB |
Output is correct |
36 |
Correct |
231 ms |
10576 KB |
Output is correct |