【POJ1151】Atlantis（线段树，扫描线）
题面
题解
学一学扫描线
其实很简单啦
这道题目要求的就是若干矩形的面积和
把扫描线平行于某个轴扫过去（我选的平行\(y\)轴扫）
这样只需要求出每次和\(x\)轴覆盖的长度
就可以两两相乘，求出面积
最后累计和就行啦
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 500
#define lson (now<<1)
#define rson (now<<1|1)
struct Node{double x1,x2,y,w;}p[MAX];
bool operator<(Node a,Node b){return a.y<b.y;}
double S[MAX];
int top;
int n,tot;
struct SegmentTreeNode
{
double ss;
int ly;
}t[MAX<<3];
void pushup(int now,int l,int r)
{
if(t[now].ly)t[now].ss=S[r+1]-S[l];
else if(l==r)t[now].ss=0;
else t[now].ss=t[lson].ss+t[rson].ss;
}
void Modify(int now,int l,int r,int L,int R,int w)
{
if(L<=l&&r<=R)
{
t[now].ly+=w;
pushup(now,l,r);
return;
}
int mid=(l+r)>>1;
if(L<=mid)Modify(lson,l,mid,L,R,w);
if(R>mid)Modify(rson,mid+1,r,L,R,w);
pushup(now,l,r);
}
int main()
{
int TT=0;
while(scanf("%d",&n))
{
++TT;
if(!n)break;
tot=top=0;
double x1,x2,y1,y2;
for(int i=1;i<=n;++i)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
p[++tot]=(Node){x1,x2,y1,1};
p[++tot]=(Node){x1,x2,y2,-1};
S[++top]=x1,S[++top]=x2;
}
sort(&S[1],&S[top+1]);
sort(&p[1],&p[tot+1]);
top=unique(&S[1],&S[top+1])-S-1;
double ans=0;
for(int i=1;i<tot;++i)
{
int l=lower_bound(&S[1],&S[top+1],p[i].x1)-S;
int r=lower_bound(&S[1],&S[top+1],p[i].x2)-S-1;
if(l<=r)Modify(1,1,top,l,r,p[i].w);
if(i!=tot)ans+=(p[i+1].y-p[i].y)*t[1].ss;
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",TT,ans);
memset(t,0,sizeof(t));
}
return 0;
}
