set.cpp

对线段进行堆排序的算法,用于几何运算,可实现对端点进行进一步排序的双重排序功能,可用于线段运算

#include <iostream>
using namespace std;
#include <stdlib.h>
#include <math.h>
struct endpoint{//flag表示左右，0为左端点
int loc[2];
bool flag;
int line;
} He[20000];
typedef struct{
  endpoint *r;
  int length;
  int listsize;
}Sqlist;
typedef Sqlist HeapType;


struct segment{  //线段的存储l为左边的点
endpoint l;        //r为右边的点，l[1]为x，l[2]为y
endpoint r; 
}s[10000];

void HeapAdjust(HeapType &H,int s, int m){
endpoint rc;
int j;
	rc=H.r[s];
for(j=2*s;j<=m;j*=2){
	if(j<m&&(H.r[j].loc[1]>H.r[j+1].loc[1]))
    ++j;
	else
		if(H.r[j].loc[1]==H.r[j+1].loc[1])  //进一步对y小的值优先
			if(H.r[j].loc[2]>H.r[j+1].loc[2])
		     j++;
				
			
   if(rc.loc[1]<H.r[j].loc[1])
	 	  break;
   else
	  if(rc.loc[1]==H.r[j].loc[1])
		  if(rc.loc[2]<=H.r[j].loc[2])
		  break;
	     		  
  H.r[s]=H.r[j];
  s=j;
}
H.r[s]=rc;
}

void HeapSort(HeapType &H){
	int i;
	
   endpoint t;
	for(i=(H.length/2);i>0;--i)
		HeapAdjust(H,i,H.length);
	for(i=H.length;i>1;--i){
	    t=H.r[1];
		H.r[1]=H.r[i];
		H.r[i]=t;
		
		HeapAdjust(H,1,i-1);
	}
}

int min(HeapType &kk)  //确定最小元素并删除
{
int j;
j=kk.r[kk.length].loc[1];
kk.r[kk.length].loc[1]=-1;
kk.length=kk.length-1;

HeapSort(kk);

return j;
}

void insert(int x,HeapType kk)//将x坐标插入到kk并维持全序，确定x坐标是否是kk的一个成员
{
kk.length=kk.length+1;
kk.r[kk.length].loc[1]=x;
HeapSort(kk);
}


int main()
{
	int i;double it1,it2;float j;  //it1,it2用来存储相对于左端点
 int x=2000;                         //增加的数量
 int y=2000;                         //
 for(i=1;i<=10000;i++){             //生成线段
	s[i].l.loc[1]=rand()%x;
  s[i].l.loc[2]=rand()%y;
  s[i].l.flag=0;
  j=rand();
  j=(int)j%360;

  if(j>=90&&j<180)
    {j=j-90;}
  else{
       if(j>=180&&j<270)
      {j=j+90;}
   }

  
  j=j/180;
  modf(20*sin(j),&it1);
  modf(20*cos(j),&it2);
  s[i].r.loc[1]=s[i].l.loc[1]+it1+1;
  s[i].r.loc[2]=s[i].l.loc[2]+it2+1;
  s[i].r.flag=1;
  s[i].l.line=i;
  s[i].r.line=i;
 }//生成线段
 



HeapType He;
He.length=0;
He.r=(endpoint*)malloc(30000*sizeof(endpoint));

for(i=1;i<=10000;i++){
He.r[2*i-1].loc[1]=s[i].l.loc[1];
He.r[2*i-1].loc[2]=s[i].l.loc[2];
He.r[2*i-1].flag=0;
He.r[2*i-1].line=i;
He.r[2*i].loc[1]=s[i].r.loc[1];
He.r[2*i].loc[2]=s[i].l.loc[2];
He.r[2*i].flag=0;
He.r[2*i].line=i;
He.length=He.length+2;
}

HeapSort(He);//把所有x放入堆中

for(i=10000;i<10100;i++)
{
	std::cout<<"x is"<<He.r[i].loc[1]<<"  y is"<<He.r[i].loc[2]<<std::endl;
}

return 0;

}