#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 100;
const ld inf = 1e9;
ld C;
struct segm{
pdd A;
pdd B;
int id;
bool operator< (const segm &t) const {
ld fa;
if(A.fi == B.fi){
fa = A.se;
}
else{
fa = (B.se-A.se)/(B.fi-A.fi) * (C - A.fi) + A.se;
}
ld fb;
if(t.A.fi == t.B.fi){
fb = t.A.se;
}
else{
fb = (t.B.se-t.A.se)/(t.B.fi-t.A.fi) * (C-t.A.fi) + t.A.se;
}
return fa < fb;
}
bool operator== (segm &t) const {
return (id == t.id);
}
};
pdd ai[N], bi[N];
pdd rig[N];
bool act[N];
int main(){
fastIO;
int n;
cin >> n;
vector<pair<pdd,int>> eve;
for(int i = 0 ; i < n; i ++) {
cin >> ai[i].fi >> ai[i].se >> bi[i].fi >> bi[i].se;
if(ai[i] > bi[i]) swap(ai[i], bi[i]);
eve.push_back(mp(ai[i],i));
eve.push_back(mp(bi[i],i));
}
set<segm> sq;
C = -inf;
sq.insert({mp(-inf,inf),mp(inf,inf),n});
rig[n]=mp(-inf,-inf);
sort(eve.begin(), eve.end());
int nid;
int cr = 0;
for(auto ii : eve){
C = ii.fi.fi;
if(!act[ii.se]){
auto it = sq.lower_bound({ai[ii.se],bi[ii.se],-1});
nid = it->id;
if(rig[nid] != mp(-inf,-inf)){
cout << (int)rig[nid].fi << " " << (int)rig[nid].se << " " << (int)ai[ii.se].fi << " " << (int)ai[ii.se].se << "\n";
}
rig[ii.se] = ii.fi;
rig[nid] = ii.fi;
act[ii.se]=true;
sq.insert({ai[ii.se],bi[ii.se],ii.se});
}
else{
sq.erase({ai[ii.se],bi[ii.se],ii.se});
auto it = sq.lower_bound({ai[ii.se],bi[ii.se],-1});
nid = it->id;
rig[nid]=ii.fi;
}
}
return 0;
}
Compilation message
roads.cpp: In function 'int main()':
roads.cpp:66:9: warning: unused variable 'cr' [-Wunused-variable]
66 | int cr = 0;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
115 ms |
8668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
3 ms |
748 KB |
Output is correct |
4 |
Correct |
25 ms |
3040 KB |
Output is correct |
5 |
Correct |
50 ms |
5616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
4 ms |
876 KB |
Output is correct |
4 |
Correct |
25 ms |
3040 KB |
Output is correct |
5 |
Correct |
54 ms |
5468 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
3 ms |
748 KB |
Output is correct |
9 |
Correct |
26 ms |
3040 KB |
Output is correct |
10 |
Correct |
348 ms |
25280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
3 ms |
748 KB |
Output is correct |
4 |
Correct |
24 ms |
3040 KB |
Output is correct |
5 |
Correct |
51 ms |
5608 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
3 ms |
748 KB |
Output is correct |
9 |
Correct |
26 ms |
3040 KB |
Output is correct |
10 |
Correct |
131 ms |
12864 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
3 ms |
748 KB |
Output is correct |
5 |
Correct |
26 ms |
3040 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
3 ms |
748 KB |
Output is correct |
9 |
Correct |
26 ms |
3040 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
3 ms |
748 KB |
Output is correct |
13 |
Correct |
24 ms |
3040 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
2 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
2 ms |
492 KB |
Output is correct |
20 |
Correct |
3 ms |
620 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
12 ms |
1384 KB |
Output is correct |
23 |
Correct |
11 ms |
1532 KB |
Output is correct |
24 |
Correct |
22 ms |
2276 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
115 ms |
8688 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
3 ms |
748 KB |
Output is correct |
6 |
Correct |
24 ms |
3040 KB |
Output is correct |
7 |
Correct |
49 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
3 ms |
748 KB |
Output is correct |
11 |
Correct |
26 ms |
3040 KB |
Output is correct |
12 |
Correct |
351 ms |
25280 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
512 KB |
Output is correct |
15 |
Correct |
3 ms |
748 KB |
Output is correct |
16 |
Correct |
24 ms |
3040 KB |
Output is correct |
17 |
Correct |
138 ms |
12964 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
3 ms |
620 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
11 ms |
1384 KB |
Output is correct |
27 |
Correct |
11 ms |
1384 KB |
Output is correct |
28 |
Correct |
22 ms |
2276 KB |
Output is correct |
29 |
Correct |
217 ms |
17488 KB |
Output is correct |
30 |
Correct |
279 ms |
24348 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
221 ms |
16592 KB |
Output is correct |
33 |
Correct |
222 ms |
16592 KB |
Output is correct |
34 |
Correct |
294 ms |
22088 KB |
Output is correct |
35 |
Correct |
309 ms |
22848 KB |
Output is correct |
36 |
Correct |
371 ms |
29084 KB |
Output is correct |