hdu1828poj1177线段树周长并

详情请见国家队1999陈宏论文

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
};
struct rectangle
{
point a,b;
};
struct node
{
int aa,bb;//左右端点值
int left,right;//左右端点编号
int flag,num,pt;
};
int tot,tt;
rectangle b[100000];
node a[100000];
void build(int x,int y)
{
int mid,now;
tot++;
now=tot;
a[now].aa=x;
a[now].bb=y;
a[now].pt=a[now].num=a[now].flag=0;
mid=(x+y)/2;
if(x!=y)
{
a[now].left=tot+1;
build(x,mid);
/*??*/
a[now].right=tot+1;
build(mid+1,y);
}
else
a[now].left=a[now].right=0;
}
bool cmp1(rectangle p1,rectangle p2)
{
if(p1.a.y<p2.a.y)return true;
return false;
}
void insert(int g,int x1,int x2,int y1,int y2)
{
int mid;
if(x1<=a[g].aa && x2>=a[g].bb && a[g].pt == 1)
{
if(y1>a[g].flag)
{
a[g].flag=y2;
a[g].num+=2;
a[g].pt=1;
}
if(y1<=a[g].flag && y2>a[g].flag)
{
a[g].flag=y2;
a[g].pt=1;
}
}
else
{
if(a[g].pt==1)
{
a[g].pt=0;
a[a[g].left].pt=a[a[g].right].pt=1;
a[a[g].left].flag=a[a[g].right].flag=a[g].flag;
a[a[g].left].num =a[a[g].right].num =a[g].num;
}
mid=(a[g].aa+a[g].bb)/2;
if(x1<=mid)
insert(a[g].left,x1,x2,y1,y2);
if(mid<x2)
insert(a[g].right,x1,x2,y1,y2);
}
}
bool cmp2(rectangle p1,rectangle p2)
{
if(p1.a.x<p2.a.x)return true;
return false;
}
void find(int g)
{
if(a[g].pt == 1)
{
tt+=(a[g].bb-a[g].aa+1)*a[g].num;
}
else
{
if(a[g].left!=0)find(a[g].left);
if(a[g].right!=0)find(a[g].right);
}
}
int main()
{
int i,n;
tot=0;
while(scanf("%d",&n)!=EOF && n)
{
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&b[i].a.x,&b[i].a.y,&b[i].b.x,&b[i].b.y);
b[i].a.x+=10001;//全部化为正数好统计
b[i].a.y+=10001;
b[i].b.x+=10001;
b[i].b.y+=10001;
}
sort(b+1,b+n+1,cmp1);
build(1,20020);
a[1].pt=1;
for(i=1;i<=n;i++)
insert(1,b[i].a.x+1,b[i].b.x,b[i].a.y,b[i].b.y);
tt=0;
find(1);
tot=0;
build(1,20020);
sort(b+1,b+n+1,cmp2);
a[1].pt=1;
for(i=1;i<=n;i++)
insert(1,b[i].a.y+1,b[i].b.y,b[i].a.x,b[i].b.x);
find(1);
printf("%dn",tt);
}
return 0;
}

最后

以上就是标致小天鹅为你收集整理的hdu1828poj1177线段树周长并的全部内容，希望文章能够帮你解决hdu1828poj1177线段树周长并所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。