2021.11.23 扫描线

2021.11.23 扫描线

http://acm.hdu.edu.cn/showproblem.php?pid=1542

扫描线求面积

#include
#include
#include
#include
using namespace std;

const int N=210;
int n,lazy[N<<5];
double X[N],tot[N<<5];
struct node{
	double l,r,h;
	int flag;
	bool operator <(const node &b)const{
		return h=L&&r<=R)return (void)(lazy[x]+=k,update(x,l,r));
	int mid=(l+r)>>1;
	if(L<=mid)add(x<<1,l,mid,L,R,k);
	if(R>mid)add(x<<1|1,mid+1,r,L,R,k);
	update(x,l,r);
}

int main(){
	int js=0;
	while(~scanf("%d",&n)&&n){
		++js;
		printf("Test case #%d\n",js);
		memset(&a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			double x,y,u,v;
			cin>>x>>y>>u>>v;
			a[i].l=a[i+n].l=x;a[i].r=a[i+n].r=u;
			a[i].h=y;a[i+n].h=v;
			a[i].flag=1;a[i+n].flag=-1;
			X[i]=x;X[i+n]=u;
		}
		sort(a+1,a+n*2+1);
		sort(X+1,X+n*2+1);
		double ans=0.0;
		int len=unique(X+1,X+n*2+1)-X-1;
		for(int i=1;i<=n*2;i++){
            //每个线段树的节点表示i到i+1这个底边区间
			int L=lower_bound(X+1,X+len+1,a[i].l)-X;
			int R=lower_bound(X+1,X+len+1,a[i].r)-X-1;
			add(1,1,len-1,L,R,a[i].flag);
			ans+=tot[1]*(a[i+1].h-a[i].h);
		}
		printf("Total explored area: %.2lf\n\n",ans);
	}
	return 0;
}

https://www.luogu.com.cn/problem/P1856

扫描线求周长

每次加入底边的长度等于这次的总底边长减去上次总底边长的绝对值；每次加入高的总长度等于总段数$\times\(2\)\times$高。

https://www.luogu.com.cn/blog/wucstdio/solution-p1856

#include
#include
#include
#include
#include
using namespace std;

const int N=1e4+10;
int n,X[N];
struct node{
	int l,r,h,flag;
	bool operator <(const node &b)const{
		return h==b.h?flag>b.flag:h=L&&r<=R)return (void)(t[x].lazy+=k,update(x));
	int mid=(l+r)>>1;
	if(L<=mid)add(x<<1,l,mid,L,R,k);
	if(R>mid)add(x<<1|1,mid+1,r,L,R,k);
	update(x);
}
inline void build(int x,int l,int r){
	t[x].l=l;t[x].r=r;t[x].num=t[x].tot=t[x].lazy=t[x].flagl=t[x].flagr=0;
	if(l==r)return ;
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	update(x);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int u,v,x,y;
		cin>>x>>y>>u>>v;
		a[i].l=a[i+n].l=x;a[i].r=a[i+n].r=u;
		a[i].h=y;a[i+n].h=v;
		a[i].flag=1;a[i+n].flag=-1;
		X[i]=x;X[i+n]=u;
	}
	sort(a+1,a+n*2+1);
	sort(X+1,X+n*2+1);
	//for(int i=1;i<=n*2;i++)cout<

#include
#include
#include
#include
using namespace std;

#define int long long
const int N=2e4+10;
int ti,n,W,H,X[N],ans;
struct node{
	int l,r,h,flag;
	bool operator <(const node &b)const{
		return h==b.h?flag>b.flag:h>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	//update(x);
}
inline void add(int x,int l,int r,int L,int R,int k){
	if(l>=L&&r<=R)return (void)(t[x].lazy+=k,t[x].maxn+=k);
	int mid=(l+r)>>1;
	pushdown(x);
	if(L<=mid)add(x<<1,l,mid,L,R,k);
	if(R>mid)add(x<<1|1,mid+1,r,L,R,k);
	update(x);
}

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>ti;
	while(ti--){
		//memset(&a,0,sizeof(a));
		cin>>n>>W>>H;
		for(int i=1;i<=n;i++){
			int x,y,u,v,val;
			cin>>x>>y>>val;
			u=x+W-1;v=y+H-1;
			a[i].l=a[i+n].l=y;a[i].r=a[i+n].r=v;
			a[i].h=x;a[i+n].h=u;
			a[i].flag=val;a[i+n].flag=-val;
			X[i]=y;X[i+n]=v;
		}
		sort(X+1,X+n*2+1);
		int len=unique(X+1,X+n*2+1)-X-1;
		sort(a+1,a+n*2+1);
		build(1,1,len-1);
		ans=0;
		for(int i=1;i<=n*2;i++){
			int L=lower_bound(X+1,X+len+1,a[i].l)-X-1;
			int R=lower_bound(X+1,X+len+1,a[i].r)-X-1;
			//cout<