#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;
int n, x[maxn], y[maxn];
int cntno, val[maxn], sz[maxn], lc[maxn], rc[maxn], prior[maxn], tr[maxn], pt[maxn];
dbl findy(int i, int xcur) {
if(x[i] == x[i+1]) return y[i];
return ((dbl) y[i+1]-y[i])/((dbl) x[i+1]-x[i])*((dbl) xcur-x[i]) + (dbl) y[i];
}
dbl findywtf(int i, int xcur, int wtf) {
if(x[i] == x[i+1]) return y[i+wtf];
return ((dbl) y[i+1]-y[i])/((dbl) x[i+1]-x[i])*((dbl) xcur-x[i]) + y[i];
}
int create(int i) {
int no = ++cntno;
pt[no] = i;
tr[i] = no;
val[no] = i;
sz[no] = 1;
prior[no] = rand();
return no;
}
void calc(int no) {
if(no == 0) return;
sz[no] = sz[lc[no]]+1+sz[rc[no]];
}
int merge(int l, int r) {
if(l == 0) return r;
if(r == 0) return l;
if(prior[l] <= prior[r]) {
rc[l] = merge(rc[l],r);
calc(l);
return l;
}
else {
lc[r] = merge(l,lc[r]);
calc(r);
return r;
}
}
pair<int,int> splitval(int no, int xcur, int y0, int idno) {
if(no == 0) return mp(0,0);
// if(xcur == 5) cout << pt[no] << " -- " << y0 << " " << findy(pt[no],xcur) << endl;
if(findy(pt[no],xcur) <= y0 || pt[no] == idno) {
auto aux = splitval(rc[no],xcur,y0,idno);
rc[no] = aux.fr;
calc(no);
return mp(no,aux.sc);
}
else {
auto aux = splitval(lc[no],xcur,y0,idno);
lc[no] = aux.sc;
calc(no);
return mp(aux.fr,no);
}
}
pair<int,int> splitsz(int no, int szlf) {
if(no == 0) return mp(0,0);
if(sz[lc[no]]+1 <= szlf) {
auto aux = splitsz(rc[no],szlf-sz[lc[no]]-1);
rc[no] = aux.fr;
calc(no);
return mp(no,aux.sc);
}
else {
auto aux = splitsz(lc[no],szlf);
lc[no] = aux.sc;
calc(no);
return mp(aux.fr,no);
}
}
int rightmost(int no) {
if(rc[no] == 0) return no;
return rightmost(rc[no]);
}
void solve() {
cin >> n;
vector<pair<pair<int,int>,pair<int,int>>> pts;
bool ok = 0;
for(int i = 1; i <= 2*n; i+=2) {
cin >> x[i] >> y[i];
cin >> x[i+1] >> y[i+1];
if(mp(x[i],y[i]) == mp(x[i+1],y[i+1])) ok = 1;
if(mp(x[i],y[i]) > mp(x[i+1],y[i+1])) {
swap(x[i],x[i+1]);
swap(y[i],y[i+1]);
}
pts.pb(mp(mp(x[i],y[i]),mp(i,1)));
pts.pb(mp(mp(x[i+1],y[i+1]),mp(i,-1)));
}
// for(int i = 1; i <= 2*n; i+= 2) {
// for(int j = 1; j <= 2*n; j+= 2) {
// if(i == j) continue;
// if(x[i+1] < x[j] || x[j+1] < x[i]) continue;
// int x1 = max(x[i],x[j]);
// int x2 = min(x[i+1],x[j+1]);
// if(findywtf(i,x1,0) <= findywtf(j,x1,0) && findywtf(i,x2,1) >= findywtf(j,x2,1)) ok = 1;
// }
// }
// if(ok) {
// cout << -1 << endl;
// return;
// }
sort(all(pts));
x[2*n+1] = -inf1;
x[2*n+2] = inf1;
y[2*n+1] = -inf1;
y[2*n+2] = -inf1;
vector<int> vec;
vec.pb(2*n+1);
int rt = create(2*n+1);
for(auto X : pts) {
if(X.sc.sc == 1) {
int i = X.sc.fr;
int xcur = X.fr.fr;
// cout << i << " put " << xcur << endl;
pair<int,int> aux;
aux = splitval(rt,xcur,y[i],i);
int rt1 = aux.fr; rt = aux.sc;
int rgt = rightmost(rt1);
if(val[rgt] != 2*n+1) {
cout << x[i] << " " << y[i] << " " << x[val[rgt]] << " " << y[val[rgt]] << endl;
}
val[rgt] = i;
int rt2 = create(i);
rt = merge(rt2,rt);
rt = merge(rt1,rt);
// int id = 0; // vec[id] is the last one under i
// for(int j = 0; j < vec.size(); j++) {
// if(findy(vec[j],xcur) <= y[i]) {
// id = j;
// }
// else {
// break;
// }
// }
// if(val[vec[id]] != 2*n+1) {
// cout << x[i] << " " << y[i] << " " << x[val[vec[id]]] << " " << y[val[vec[id]]] << endl;
// }
// val[vec[id]] = i;
// val[i] = i;
// vector<int> newvec;
// for(int j = 0; j <= id; j++) {
// newvec.pb(vec[j]);
// }
// newvec.pb(i);
// for(int j = id+1; j < vec.size(); j++) {
// newvec.pb(vec[j]);
// }
// swap(vec,newvec);
}
else {
int i = X.sc.fr;
int xcur = X.fr.fr;
// cout << i << " tak " << xcur << endl;
pair<int,int> aux;
aux = splitval(rt,xcur,y[i+1],i);
int rt1 = aux.fr; rt = aux.sc;
// cout << rt1 << " " << rt << endl;
aux = splitsz(rt1,sz[rt1]-1);
int rt2 = aux.sc; rt1 = aux.fr;
int rgt = rightmost(rt1);
val[rgt] = i+1;
rt = merge(rt1,rt);
// cout << rgt << " " << pt[rgt] << " " << pt[rt] << endl;
}
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
Compilation message
roads.cpp: In function 'void solve()':
roads.cpp:195:17: warning: unused variable 'rt2' [-Wunused-variable]
195 | int rt2 = aux.sc; rt1 = aux.fr;
| ^~~
roads.cpp:100:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
100 | bool ok = 0;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
68 ms |
7112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
596 KB |
Output is correct |
4 |
Correct |
9 ms |
2604 KB |
Output is correct |
5 |
Correct |
21 ms |
4516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
596 KB |
Output is correct |
4 |
Correct |
10 ms |
2632 KB |
Output is correct |
5 |
Correct |
24 ms |
4420 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
11 ms |
2500 KB |
Output is correct |
10 |
Correct |
167 ms |
19460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
596 KB |
Output is correct |
4 |
Correct |
10 ms |
2576 KB |
Output is correct |
5 |
Correct |
19 ms |
4428 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
10 ms |
2452 KB |
Output is correct |
10 |
Correct |
56 ms |
9872 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
556 KB |
Output is correct |
5 |
Correct |
11 ms |
2640 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
11 ms |
2420 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
13 |
Correct |
11 ms |
2504 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
352 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
588 KB |
Output is correct |
21 |
Correct |
1 ms |
328 KB |
Output is correct |
22 |
Correct |
5 ms |
1240 KB |
Output is correct |
23 |
Correct |
5 ms |
1240 KB |
Output is correct |
24 |
Correct |
11 ms |
1868 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
76 ms |
7176 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
564 KB |
Output is correct |
6 |
Correct |
15 ms |
2512 KB |
Output is correct |
7 |
Correct |
22 ms |
4312 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
11 ms |
2512 KB |
Output is correct |
12 |
Correct |
167 ms |
19284 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
10 ms |
2512 KB |
Output is correct |
17 |
Correct |
50 ms |
10004 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
468 KB |
Output is correct |
23 |
Correct |
2 ms |
468 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
6 ms |
1240 KB |
Output is correct |
27 |
Correct |
5 ms |
1240 KB |
Output is correct |
28 |
Correct |
11 ms |
1876 KB |
Output is correct |
29 |
Correct |
84 ms |
10972 KB |
Output is correct |
30 |
Correct |
96 ms |
15080 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
109 ms |
12600 KB |
Output is correct |
33 |
Correct |
108 ms |
12612 KB |
Output is correct |
34 |
Correct |
167 ms |
16552 KB |
Output is correct |
35 |
Correct |
192 ms |
17196 KB |
Output is correct |
36 |
Correct |
165 ms |
18016 KB |
Output is correct |