分治法解决凸包问题
#include
typedef struct {
int x,y;
}Point;
int arrayLength=0;
int main()
{
printf("**************软件工程3班**************");
printf("*****************成冠辉*****************");
Point array[15],result[15];
InitialData(array);
printf("请输入数据：\n\n");
Put(array,arrayLength);
Qsort(array,0,arrayLength-1);
printf("排序后：\n");
Put(array,arrayLength);
GetResult(array,result);
printf("结果集为：\n");
Put(result,resultCount);
getchar();
return 0;
}
//返回分裂位置
int Partition(Point *array,int l,int r)
{
int p=l,i=l,j=r+1;
do
{
do
{
i++;
}while(array[i].x
do
{
j--;
}while(array[j].x>array[p].x);
swap(array,i,j);
}while(i
swap(array,i,j);
swap(array,p,j);
return j;
}
//用快排将x坐标的值从大到小
void Qsort(Point *array,int l,int r)
{
int s=0;
if(l
{
s=Partition(array,l,r); //分裂位置
Qsort(array,l,s-1);
Qsort(array,s+1,r);
}
}
//打印
void Put(Point *array,int length)
{
for(int i=0;i
{
printf("%d\t%d\n",array[i].x,array[i].y);
}
printf("\n");
}
void GetResult(Point *array,Point *result)
{
Add(array,result); //将首尾两个点并入result[15]
DealWithLeft(0,14,array,result); //处理array[0]->array[14]射线左边的点
DealWithLeft(14,0,array,result); //处理array[14]->array[0]射线右边的点
}
void InitialData(Point *array)
{
FILE *fp=freopen("input.txt","r",stdin);
char ch;
Point* currentPoint=array;
for(int i=0;ch!=EOF;i++)
{
scanf("%d%d",&array[i].x,&array[i].y);
ch=fgetc(fp);
arrayLength++;
}
fclose(fp);
}
void swap(Point *array,int i,int j)
{
if(i
{
int x=0,y=0;
x=array[i].x;
y=array[i].y;
array[i].x=array[j].x;
array[i].y=array[j].y;
array[j].x=x;
array[j].y=y;
}
}
int resultCount=0; //插入值的个数
void Add(Point *array,Point *result)
{
result[resultCount].x=array[0].x;
result[resultCount++].y=array[0].y;
result[resultCount].x=array[14].x;
result[resultCount++].y=array[14].y;
}
void Add(Point *array,Point *result,int i)
{
result[resultCount].x=array[i].x;
result[resultCount++].y=array[i].y;
}
//处理array[first]->array[final]射线左侧的点
void DealWithLeft(int first,int final,Point *array,Point *result)
{
int max=0,index=-1;
int i=first;
if(firstarray[final]射线左侧
{
for(i;i
{
int x1 = array[first].x,y1 = array[first].y;
int x2 = array[final].x,y2 = array[final].y;
int x3 = array[i].x,y3 = array[i].y;
int compute = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;
if(compute > max)
{
max = compute;
index = i;
}
}
}
else
{
for(i;i>=0;i--)//array[final]->array[first]射线左侧
{
int x1 = array[first].x,y1 = array[first].y;
int x2 = array[final].x,y2 = array[final].y;
int x3 = array[i].x,y3 = array[i].y;
int compute = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;
if(compute > max)
{
max = compute;
index = i;
}
}
}
if(index!=-1) //取到array[index]（即最高点） ，这个点与array[final]、array[first]构成的三角形面积最大
{
Add(array,result,index);
} } DealWithLeft(first,index,array,result); DealWithLeft(index,final,array,result);