Rexdf

The devil is in the Details.

坑爹的hdu3265

| Comments

起源于在做这道经典的扫描线的题目的时候，采用了按照我的思维倾向，横轴优先，那么就用竖轴做线段树，思路很简单。这里有两种划分的方法 两种不同的分割方法 问题出在，从左向右的用扫描线的时候，按照左图的方式是是无限的Stack_Overflow的，而我本地测试了多组10000+的随机最大范围数据，对拍均是正常的。 至今任然想不明白是否是我线段树实现的问题，还是题目stack限制的问题。理论上区区线段树不可能出现stack_overflow的啊！！求大神解释

怪异的事情MyBlog
for(int j=0;j<4;j++)scanf("%d%d",&x[j],&y[j]);

//非常奇怪，如果用注释里面的切割方式则一直是stack_overflow 

//这里是一||一的切割方式，此方式STack_Overflow无数遍，无论hdu还是poj 

/*SIDE[cnt1++]=Edge(x[0],y[2],y[3],1);

SIDE[cnt1++]=Edge(x[2],y[2],y[3],-1);

SIDE[cnt1++]=Edge(x[3],y[2],y[3],1);

SIDE[cnt1++]=Edge(x[1],y[2],y[3],-1);

            

SIDE[cnt1++]=Edge(x[0],y[3],y[1],1);

SIDE[cnt1++]=Edge(x[1],y[3],y[1],-1);

SIDE[cnt1++]=Edge(x[0],y[0],y[2],1);

SIDE[cnt1++]=Edge(x[1],y[0],y[2],-1);*/

//下面是I二I的切割方式 

SIDE[cnt1++]=Edge(x[0],y[0],y[1],1);

SIDE[cnt1++]=Edge(x[2],y[0],y[1],-1);

 
SIDE[cnt1++]=Edge(x[2],y[0],y[2],1);

SIDE[cnt1++]=Edge(x[2],y[3],y[1],1);

 
SIDE[cnt1++]=Edge(x[3],y[0],y[2],-1);

SIDE[cnt1++]=Edge(x[3],y[3],y[1],-1);

 
SIDE[cnt1++]=Edge(x[3],y[0],y[1],1);

SIDE[cnt1++]=Edge(x[1],y[0],y[1],-1);

Comments