萌新刚学OI,写的扫描线只能过样例
查看原帖
萌新刚学OI,写的扫描线只能过样例
113926
typedef楼主2020/8/24 21:51

代码奉上:

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((t[p].l+t[p].r)>>1) 
using namespace std;
const int N=1e5+6;
int n,m,num;
struct P{
	double x,y,z;
	int k;
	inline bool operator < (const P &o) const{
		return x<o.x;
	}
}a[N<<1];
double raw[N<<1];
map<double,int> val;
struct T{
	int l,r,cnt;
	double len;
}t[N<<3];
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].cnt=0,t[p].len=0;
	if(l==r) return;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void change(int p,int l,int r,double k){
	if(l<=t[p].l&&r>=t[p].r){
		t[p].len=((t[p].cnt+=k)?raw[t[p].r+1]-raw[t[p].l]:(t[p].l==t[p].r?0:t[ls].len+t[rs].len));
		return;
	}//段加一是点                         ↑               断了     单点长度为零  子区间的覆盖长度值                                          
	if(l<=mid) change(ls,l,r,k);
	if(r>mid) change(rs,l,r,k);
	t[p].len=(t[p].cnt?raw[t[p].r+1]-raw[t[p].l]:t[ls].len+t[rs].len);
	//        全不全?       不全就整个区间           断了就左子区间加右子区间   ****ooo******
	//                                                                           *************               
	return; 
}
inline void Atlantis(){
	for(int i=1;i<=n;i++){
		int k=i<<1;//第i对 
		double y,z;//y1,y2;
		scanf("%lf%lf%lf%lf",&a[k-1].x,&y,&a[k].x,&z);//四元组 
		raw[k-1]=a[k-1].y=a[k].y=y;
		raw[k]=a[k-1].z=a[k].z=z;
		a[k-1].k=1,a[k].k=-1;
	}
	n<<=1;//n个矩形,2n个坐标
	sort(raw+1,raw+n+1);//按x排序
	int m=unique(raw+1,raw+n+1)-raw-1;//去重后的个数
	for(int i=1;i<=m;i++){
		val[raw[i]]=i;//建立映射关系 
	} 
	sort(a+1,a+n+1);//四元组按x排序 
	build(1,1,m-1);//m个点,m-1个区间 
	double ans=0;//面积
	for(int i=1;i<n;i++){//共2n-1个区间 
		int y=val[a[i].y];//y1对应离散值 
		int z=val[a[i].z]-1;//y2对应离散值
		change(1,y,z,a[i].k);
		ans+=t[1].len*(a[i+1].x-a[i].x);//加上 
	}//扫过的面积 
	printf("%.0lf\n",ans);
}
int main(){
//	freopen("testin.txt","r",stdin);
//	freopen("testout.txt","w",stdout);
	while(cin>>n&&n) Atlantis();
	return 0;
}

大佬们有时间的话帮忙查下错,没时间就算了QwQ

2020/8/24 21:51
加载中...