# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
345996 |
2021-01-08T20:51:59 Z |
doowey |
Roads (CEOI20_roads) |
C++14 |
|
189 ms |
8028 KB |
#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<ld,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].fi,i));
eve.push_back(mp(bi[i].fi,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;
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 << rig[nid].fi << " " << rig[nid].se << " " << ai[ii.se].fi << " " << ai[ii.se].se << "\n";
}
rig[ii.se] = ai[ii.se];
rig[nid] = ai[ii.se];
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]=bi[ii.se];
}
}
return 0;
}
Compilation message
roads.cpp: In function 'int main()':
roads.cpp:66:9: warning: unused variable 'cr' [-Wunused-variable]
66 | int cr = 0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
189 ms |
8028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Incorrect |
5 ms |
620 KB |
Expected integer, but "1.00081e+06" found |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Incorrect |
5 ms |
620 KB |
Expected integer, but "1.00081e+06" found |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Incorrect |
7 ms |
620 KB |
Expected integer, but "1.00081e+06" found |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Incorrect |
5 ms |
620 KB |
Expected integer, but "1.00081e+06" found |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
187 ms |
8028 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Incorrect |
5 ms |
640 KB |
Expected integer, but "1.00081e+06" found |
6 |
Halted |
0 ms |
0 KB |
- |