Arrtan_73 @ 2024-07-16 11:38:35
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct line{
int xa, xb, ya, yb;
double b, k;
double operator [](int x){return k * x + b;}
bool operator <(line x){return x.xa > xa;}
}lin[N];
int temp[N << 1], top;
int siz, n, ans;
int tree[N << 3];
bool cmp(const line a, const int b){return a.xa <= b;}
void addline(int id){
lin[id].k = (double)(lin[id].ya - lin[id].yb) / (lin[id].xa - lin[id].xb);
lin[id].b = (double)lin[id].ya - lin[id].k * lin[id].xa;
return;
}
void add(int p, int L, int R, int l, int r, int id){
int mid = (L + R) >> 1;
if(l <= L && R <= r){
if(!tree[p] || (lin[tree[p]][L] < lin[id][L] && lin[tree[p]][R] < lin[id][R])){
tree[p] = id;
return;
}
if(L == R || (lin[tree[p]][L] > lin[id][L] && lin[tree[p]][R] > lin[id][R]))return;
if(lin[tree[p]][mid] < lin[id][mid])swap(tree[p], id);
if(lin[tree[p]][L] <= lin[id][L])add(p << 1, L, mid, l, r, id);
else if(lin[tree[p]][R] <= lin[id][R])add(p << 1, mid + 1, R, l, r, id);
}
else{
if(l <= mid)add(p << 1, L, mid, l, r, id);
if(mid < r)add(p << 1 | 1, mid + 1, R, l, r, id);
}
return;
}
void getans(int p, int L, int R, int k){
if(tree[p] && lin[tree[p]][k] > lin[ans][k])ans = tree[p];
if(L == R)return;
int mid = (L + R) / 2;
if(k <= mid)getans(p * 2, L, mid, k);
else getans(p * 2 + 1, mid + 1, R, k);
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
lin[0].k = lin[0].b = -1;
for(int i = 1; i <= n; i++){
cin >> lin[i].xa >> lin[i].ya >> lin[i].xb >> lin[i].yb;
temp[++top] = lin[i].xa;
temp[++top] = lin[i].xb;
}
sort(temp + 1, temp + top + 1);
sort(lin + 1, lin + n + 1);
top = unique(temp + 1, temp + top + 1) - (temp + 1);
for(int i = 1; i <= n; i++){
lin[i].xa = lower_bound(temp + 1, temp + top + 1, lin[i].xa) - temp;
lin[i].xb = lower_bound(temp + 1, temp + top + 1, lin[i].xb) - temp;
addline(i);
//cout << lin[i].xa << " " << lin[i].ya << " " << lin[i].xb << " " << lin[i].yb << " " << lin[i].b << " " << lin[i].k << endl;
}
int cnt = 1, pos = 1, ed = 0;
while(1){
int r = lower_bound(lin + 1, lin + n + 1, lin[pos].xb, cmp) - (lin + 1);
//cout << r << endl;
for(int i = ed + 1; i <= r; i++){
//cout << lin[pos][lin[i].xa] << endl;
if(lin[i].ya <= lin[pos][lin[i].xa])add(1, 0, N << 1, lin[i].xa, lin[i].xb, i);
}
ed = r;
ans = 0;
getans(1, 0, N << 1, lin[pos].xb + 1);
//cout << ans << endl;
if(ans)pos = ans, cnt++;
else break;
}
cout << cnt;
return 0;
}
/*
2
0 0 1 3
4 5 7 6
*/
by Arrtan_73 @ 2024-07-16 11:38:52
只有 65pts
by Arrtan_73 @ 2024-07-16 11:58:02
else if(lin[tree[p]][R] <= lin[id][R])add(p << 1, mid + 1, R, l, r, id);
改为
else if(lin[tree[p]][R] <= lin[id][R])add(p << 1 | 1, mid + 1, R, l, r, id);
by Arrtan_73 @ 2024-07-16 11:58:21
但还是错的