求调
查看原帖
求调
736527
Arrtan_73楼主2024/7/16 11:38
#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
*/
2024/7/16 11:38
加载中...