程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1542 線段樹+掃描線+離散化

hdu1542 線段樹+掃描線+離散化

編輯：C++入門知識

hdu1542 線段樹+掃描線+離散化

只想說題目給的欲實際不服還是這類型的水題吧建議看之前我寫的那個

#include

#include
#include
#include
using namespace std;
#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)

int n;
struct node
{
double y;
int x1,x2;
int flash;
}A[31000];
struct Node
{
int ii;
double x;
}change[35000];
int cmp1(Node a,Node b)
{
return a.x }
int cmp2(node a,node b)
{
return a.y }
int num[80000];
double map[31000];
int update(int L,int R,int left,int right,int k,int mark)
{
int mid=(L+R)/2;
if(L==left&&right==R)
{
if(num[mark]!=-1)
{
num[mark]+=k;
return 0;
}
update(L,mid,L,mid,k,LL(mark));
update(mid,R,mid,R,k,RR(mark));
if(num[LL(mark)]==num[RR(mark)]) num[mark]=num[LL(mark)];
else num[mark]=-1;
}
else
{
if(num[mark]>=0)
{
num[LL(mark)]=num[RR(mark)]=num[mark];
}
if(right<=mid)
{
update(L,mid,left,right,k,LL(mark));
}
else if(left>=mid)
{
update(mid,R,left,right,k,RR(mark));
}
else
{
update(L,mid,left,mid,k,LL(mark));
update(mid,R,mid,right,k,RR(mark));
}
if(num[LL(mark)]==num[RR(mark)]) num[mark]=num[LL(mark)];
else num[mark]=-1;
}
return 0;
}
double find(int L,int R,int mark)
{
double Long=0;
if(num[mark]>=1)
{
Long+=map[R]-map[L];
return Long;
}
if(num[mark]==0) return 0;
int mid=(L+R)/2;
Long+=find(L,mid,LL(mark))+find(mid,R,RR(mark));
return Long;
}
int main()
{
int i,j,d=1;
double x1,y1,x2,y2;
while(~scanf("%d",&n),n)
{
n*=2;
//j=0;
memset(A,0,sizeof(A));
memset(map,0,sizeof(map));
memset(change,0,sizeof(change));
for(i=1;i<=n;i+=2)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
A[i].y=y1;
A[i].flash=1;
A[i+1].y=y2;
A[i+1].flash=-1;
change[i].x=x1;
change[i+1].ii=change[i].ii=i;
change[i+1].x=x2;
}
int leap[10000];
memset(leap,0,sizeof(leap));
sort(change+1,change+1+n,cmp1);
int j=0;
double k=-1;
for(i=1;i<=n;i++)
{
if(change[i].x!=k)
{
k=change[i].x;
++j;
map[j]=change[i].x;
}
if(leap[change[i].ii]==0)
{
A[change[i].ii].x1=A[change[i].ii+1].x1=j;
leap[change[i].ii]=1;
}
else A[change[i].ii].x2=A[change[i].ii+1].x2=j;
}
sort(A+1,A+1+n,cmp2);
memset(num,0,sizeof(num));
update(1,j,A[1].x1,A[1].x2,1,1);
double area=0;
for(i=2;i<=n;i++)
{
area+=find(1,j,1)*(A[i].y-A[i-1].y);
if(A[i].flash==1)
update(1,j,A[i].x1,A[i].x2,1,1);
else update(1,j,A[i].x1,A[i].x2,-1,1);
}
printf("Test case #%d\n",d++);
printf("Total explored area: %.2lf\n",area);
printf("\n");
}
return 0;
}