第一次做扫描线
挺好的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct ppx {
int l,r;
double left,right;
double len;
int cover;//记录重边情况
} tree[4*200+10];
double y[200+10];//对应的序号装对应的边
struct pp {
double x;
double y1,y2;
int flag;//标记入边还是出边
} node[200+10];
bool cmp(pp s,pp t) {
return s.x<t.x;
}
void build(int rt,int left,int right) {
tree[rt].l=left;
tree[rt].r=right;
tree[rt].left=y[left];
tree[rt].right=y[right];
tree[rt].len=0;
tree[rt].cover=0;
if(tree[rt].l+1==tree[rt].r) {
return ;
}
int m=(left+right)/2;
build(rt<<1,left,m);
build((rt<<1)+1,m,right);
}
void solve(int rt) {
if(tree[rt].cover>0) {
tree[rt].len=tree[rt].right-tree[rt].left;//求这段区间长度
} else if(tree[rt].r-tree[rt].l==1) { //长度清0
tree[rt].len=0;
} else {
tree[rt].len=tree[rt<<1].len+tree[(rt<<1)+1].len;//长度递归到线段树的根
}
}
void updata(int rt,pp b) { //写那么复杂为了节省时间
if(b.y1==tree[rt].left&&b.y2==tree[rt].right) { //区间查找嘛。。。
tree[rt].cover+=b.flag;
} else if(b.y2<=tree[rt<<1].right) { //找左子树。。。
updata(rt<<1,b);
} else if(b.y1>=tree[(rt<<1)+1].left) { //找右子树。。。。
updata((rt<<1)+1,b);
} else { //分成两段。。。。左子树和右子树，。。。。
pp temp;
temp=b;
temp.y2=tree[rt<<1].right;
updata(rt<<1,temp);
temp=b;
temp.y1=tree[(rt<<1)+1].left;
updata((rt<<1)+1,temp);
}
solve(rt);//区间的长度更新啦
}
int main() {
int n,cases=1;
while(~scanf("%d",&n)&&n) {
int t=1;
for(int i=1; i<=n; i++) {
scanf("%lf%lf",&node[t].x,&y[t]);
scanf("%lf%lf",&node[t+1].x,&y[t+1]);
node[t].y1=y[t];
node[t].y2=y[t+1];
node[t+1].y1=y[t];
node[t+1].y2=y[t+1];
node[t].flag=1;
node[t+1].flag=-1;
t+=2;
}
sort(node+1,node+t,cmp);
sort(y+1,y+t);
build(1,1,t-1);//为啥t-1，因为现在t比序号大一了。。。因为上面的循环
updata(1,node[1]);//先算第一条边。。。
double sum=0;
for(int i=2; i<t; i++) {
sum+=tree[1].len*(node[i].x-node[i-1].x);//瞅见没，这就是求面积的。。// printf("%lf %lf\n",node[i].x-node[i-1].x,tree[1].len);
updata(1,node[i]);
}
printf("Test case #%d\n",cases++);
printf("Total explored area: %.2f\n\n",sum);
}
}