POJ1839
//终于做出来第一题扫描线了，纠结了好久，纪念一下
//关键在于画图理解
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int left,right;
int num,len;
}tree[50005*4];
struct line
{
int x1,x2,flag,y;
}lines[2020];
bool cmp(const struct line &a,const struct line &b)
{
return a.y<b.y;
}
void build(int left,int right,int now)
{
tree[now].left=left;
tree[now].right=right;
tree[now].num=tree[now].len=0;
if((left+1)==right)
return ;
int mid=(left+right)/2;
build(left,mid,now*2);
build(mid,right,now*2+1);
}
void getlen(int now)//这个对于理解扫描线很重要
{
if(tree[now].num > 0)
tree[now].len =tree[now].right - tree[now].left;
else
if(tree[now].left+1 == tree[now].right)
tree[now].len = 0;
else
tree[now].len = tree[now* 2].len + tree[now* 2 + 1].len;
}
void update(int now,int id)
{
if(tree[now].left >= lines[id].x1 && tree[now].right <= lines[id].x2)
{
tree[now].num+=lines[id].flag;
getlen(now);
return;
}
if(tree[now].left+1==tree[now].right)
return ;
int mid = (tree[now].right+tree[now].left)/2;
if(lines[id].x1>= mid)
{
update(now* 2 + 1,id);
}
else
{
if(lines[id].x2<= mid)
{
update(now* 2,id);
}
else
{
update(now* 2,id);
update(now* 2 + 1,id);
}
}
getlen(now);
}
int main()
{
int a,b,c,d;
while(cin>>a>>b>>c>>d && (a+b+c+d)!=-4)
{
int linenum=0;
lines[linenum].x1=a;
lines[linenum].x2=c;
lines[linenum].flag=1;
lines[linenum++].y=b;
lines[linenum].x1=a;
lines[linenum].x2=c;
lines[linenum].flag=-1;
lines[linenum++].y=d;
while(cin>>a>>b>>c>>d && (a+b+c+d)!=-4)
{
lines[linenum].x1=a;
lines[linenum].x2=c;
lines[linenum].flag=1;
lines[linenum++].y=b;
lines[linenum].x1=a;
lines[linenum].x2=c;
lines[linenum].flag=-1;
lines[linenum++].y=d;
}
build(0,50010,1);
sort(lines,lines+linenum,cmp);
update(1,0);
int ans=0;
for (int i=1;i<linenum;i++)
{
//cout<<tree[1].len<<endl;
ans+=(lines[i].y-lines[i-1].y)*tree[1].len;
update(1,i);
}
cout << ans << endl;
}
return 0;
}
优质内容筛选与推荐>>1、测试网
2、ESXi 5.0嵌套虚拟Windows 2008R2 & Hyper-V Server并能启用64位VM的方法
3、Blog 小技巧
4、Vue学习笔记之Vue的模板字符串
5、【Zabbix】zabbix设置邮件报警